Idea: awoo
Tutorial
Tutorial is loading...
Solution (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int tc;
scanf("%d", &tc);
while (tc--){
int n;
scanf("%d", &n);
int p = 0, c = 0;
bool fl = true;
forn(i, n){
int x, y;
scanf("%d%d", &x, &y);
if (x < p || y < c || y - c > x - p)
fl = false;
p = x, c = y;
}
puts(fl ? "YES" : "NO");
}
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val (n, x) = readLine()!!.split(' ').map { it.toInt() }
val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending()
var cnt = 0
var sum = 0L
while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) {
sum += a[cnt]
cnt++
}
println(cnt)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long li;
const int N = 300 * 1000 + 13;
int n;
li a[N], b[N];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%lld%lld", &a[i], &b[i]);
li ans = 0, mn = 1e18;
forn(i, n) {
int ni = (i + 1) % n;
li val = min(a[ni], b[i]);
ans += a[ni] - val;
mn = min(mn, val);
}
ans += mn;
printf("%lld\n", ans);
}
int main() {
int T;
scanf("%d", &T);
forn(i, T)
solve();
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
int n;
li l, r;
inline bool read() {
if(!(cin >> n >> l >> r))
return false;
return true;
}
bool intersect(li l1, li r1, li l2, li r2) {
return min(r1, r2) > max(l1, l2);
}
vector<int> ans;
void calc(int lf, int rg, li &id) {
if(lf == rg) return;
if(intersect(l, r, id, id + 2 * (rg - lf))) {
fore(to, lf + 1, rg + 1) {
if(l <= id && id < r)
ans.push_back(lf);
id++;
if(l <= id && id < r)
ans.push_back(to);
id++;
}
} else
id += 2 * (rg - lf);
calc(lf + 1, rg, id);
if(lf == 0) {
if(l <= id && id < r)
ans.push_back(lf);
id++;
}
}
inline void solve() {
ans.clear();
li id = 0;
l--;
calc(0, n - 1, id);
assert(sz(ans) == r - l);
assert(id == n * li(n - 1) + 1);
for(int v : ans)
cout << v + 1 << " ";
cout << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
long long d;
scanf("%lld", &d);
int q;
scanf("%d", &q);
vector<long long> primes;
for (long long i = 2; i * i <= d; ++i) if (d % i == 0){
primes.push_back(i);
while (d % i == 0) d /= i;
}
if (d > 1){
primes.push_back(d);
}
vector<int> fact(100), rfact(100);
fact[0] = 1;
for (int i = 1; i < 100; ++i)
fact[i] = mul(fact[i - 1], i);
rfact[99] = binpow(fact[99], MOD - 2);
for (int i = 98; i >= 0; --i)
rfact[i] = mul(rfact[i + 1], i + 1);
forn(i, q){
long long x, y;
scanf("%lld%lld", &x, &y);
vector<int> up, dw;
for (auto p : primes){
int cnt = 0;
while (x % p == 0){
--cnt;
x /= p;
}
while (y % p == 0){
++cnt;
y /= p;
}
if (cnt < 0) dw.push_back(-cnt);
else if (cnt > 0) up.push_back(cnt);
}
int ans = 1;
ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]);
for (auto it : up) ans = mul(ans, rfact[it]);
ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]);
for (auto it : dw) ans = mul(ans, rfact[it]);
printf("%d\n", ans);
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const li INF64 = li(1e18);
const int N = 500043;
li f[N];
li get(int x)
{
li ans = 0;
for (; x >= 0; x = (x & (x + 1)) - 1)
ans += f[x];
return ans;
}
void inc(int x, li d)
{
for (; x < N; x = (x | (x + 1)))
f[x] += d;
}
li get(int l, int r)
{
return get(r) - get(l - 1);
}
li dp[N];
int a[N], b[N], p[N];
int n, m;
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < n; i++)
scanf("%d", &p[i]);
scanf("%d", &m);
for(int i = 0; i < m; i++)
scanf("%d", &b[i]);
for(int i = 0; i < n; i++)
dp[i] = -INF64;
map<int, vector<int> > pos;
for(int i = 0; i < n; i++)
pos[a[i]].push_back(i);
set<pair<int, int> > q;
for(int i = 0; i < n; i++)
q.insert(make_pair(a[i], i));
for(auto x : pos[b[0]])
dp[x] = p[x];
while(!q.empty() && q.begin()->first <= b[0])
{
int k = q.begin()->second;
q.erase(q.begin());
if(p[k] > 0)
inc(k, p[k]);
}
for(int i = 1; i < m; i++)
{
int i1 = b[i - 1], i2 = b[i];
vector<int> both_pos;
for(auto x : pos[i1])
both_pos.push_back(x);
for(auto x : pos[i2])
both_pos.push_back(x);
li best = -INF64;
int last = -1;
sort(both_pos.begin(), both_pos.end());
for(auto x : both_pos)
{
best += get(last + 1, x);
last = x;
if(a[x] == i1)
best = max(best, dp[x]);
else
dp[x] = best + p[x];
}
while(!q.empty() && q.begin()->first <= i2)
{
int k = q.begin()->second;
q.erase(q.begin());
if(p[k] > 0)
inc(k, p[k]);
}
}
li best_dp = -INF64;
for(int i = 0; i < n; i++)
if(a[i] == b[m - 1])
best_dp = max(best_dp, dp[i] + get(i + 1, n - 1));
li ans = 0;
for(int i = 0; i < n; i++)
ans += p[i];
ans -= best_dp;
if(ans > li(1e15))
puts("NO");
else
printf("YES\n%lld\n", ans);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < n; i++)
#define sz(a) ((int)(a).size())
const int LOGN = 20;
const int N = (1 << LOGN);
typedef long double ld;
typedef long long li;
const ld PI = acos(-1.0);
struct comp
{
ld x, y;
comp(ld x = .0, ld y = .0) : x(x), y(y) {}
inline comp conj() { return comp(x, -y); }
};
inline comp operator +(const comp &a, const comp &b)
{
return comp(a.x + b.x, a.y + b.y);
}
inline comp operator -(const comp &a, const comp &b)
{
return comp(a.x - b.x, a.y - b.y);
}
inline comp operator *(const comp &a, const comp &b)
{
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline comp operator /(const comp &a, const ld &b)
{
return comp(a.x / b, a.y / b);
}
vector<comp> w[LOGN];
vector<int> rv[LOGN];
void precalc()
{
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, comp());
for(int k = 0; k < (1 << st); k++)
{
double ang = PI / (1 << st) * k;
w[st][k] = comp(cos(ang), sin(ang));
}
rv[st].assign(1 << st, 0);
if(st == 0)
{
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
for(int k = 0; k < (1 << st); k++)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
inline void fft(comp a[N], int n, int ln, bool inv)
{
for(int i = 0; i < n; i++)
{
int ni = rv[ln][i];
if(i < ni)
swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++)
{
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1))
{
for(int pos = k; pos < k + len; pos++)
{
comp l = a[pos];
comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
a[pos] = l + r;
a[pos + len] = l - r;
}
}
}
if(inv) for(int i = 0; i < n; i++)
a[i] = a[i] / n;
}
comp aa[N];
comp bb[N];
comp cc[N];
inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc)
{
int n = 1, ln = 0;
while(n < (sza + szb))
n <<= 1, ln++;
for(int i = 0; i < n; i++)
aa[i] = (i < sza ? a[i] : comp());
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : comp());
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = aa[i] * bb[i];
fft(cc, n, ln, true);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
}
comp a[N];
comp b[N];
comp c[N];
vector<int> p_function(const vector<int>& v)
{
int n = v.size();
vector<int> p(n);
for(int i = 1; i < n; i++)
{
int j = p[i - 1];
while(j > 0 && v[j] != v[i])
j = p[j - 1];
if(v[j] == v[i])
j++;
p[i] = j;
}
return p;
}
int p[26];
char buf[N];
string s, t;
int main()
{
precalc();
for(int i = 0; i < 26; i++)
{
scanf("%d", &p[i]);
p[i]--;
}
scanf("%s", buf);
s = buf;
scanf("%s", buf);
t = buf;
int n = s.size();
int m = t.size();
vector<int> color(26, 0);
vector<vector<int> > cycles;
for(int i = 0; i < 26; i++)
{
if(color[i])
continue;
vector<int> cycle;
int cc = cycles.size() + 1;
int cur = i;
while(color[cur] == 0)
{
cycle.push_back(cur);
color[cur] = cc;
cur = p[cur];
}
cycles.push_back(cycle);
}
vector<int> ans(m - n + 1);
vector<int> s1, t1;
for(int i = 0; i < n; i++)
s1.push_back(color[int(s[i] - 'a')]);
for(int i = 0; i < m; i++)
t1.push_back(color[int(t[i] - 'a')]);
vector<int> st = s1;
st.push_back(0);
for(auto x : t1)
st.push_back(x);
vector<int> pf = p_function(st);
for(int i = 0; i < m - n + 1; i++)
if(pf[2 * n + i] == n)
ans[i] = 1;
map<char, comp> m1, m2;
for(auto cur : cycles)
{
int k = cur.size();
for(int i = 0; i < k; i++)
{
ld ang1 = 2 * PI * i / k;
ld ang2 = (PI - 2 * PI * i) / k;
m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1));
m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2));
}
}
ld ideal = 0;
for(int i = 0; i < n; i++)
ideal += (m1[s[i]] * m2[s[i]]).x;
reverse(s.begin(), s.end());
for(int i = 0; i < n; i++)
a[i] = m1[s[i]];
for(int i = 0; i < m; i++)
b[i] = m2[t[i]];
int szc;
multiply(a, n, b, m, c, szc);
for(int i = 0; i < m - n + 1; i++)
if(fabsl(c[i + n - 1].x - ideal) > 0.01)
ans[i] = 0;
for(int i = 0; i < m - n + 1; i++)
printf("%d", ans[i]);
return 0;
}