Submission #958840

#TimeUsernameProblemLanguageResultExecution timeMemory
958840gaga999Fish 2 (JOI22_fish2)C++17
0 / 100
120 ms78676 KiB
// #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define lowbit(x) ((x) & -(x)) #define ml(a, b) ((1ll * (a) * (b)) % M) #define tml(a, b) (a) = ((1ll * (a) * (b)) % M) #define ad(a, b) ((0ll + (a) + (b)) % M) #define tad(a, b) (a) = ((0ll + (a) + (b)) % M) #define mi(a, b) ((0ll + M + (a) - (b)) % M) #define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M) #define tmin(a, b) (a) = min((a), (b)) #define tmax(a, b) (a) = max((a), (b)) #define iter(a) (a).begin(), (a).end() #define riter(a) (a).rbegin(), (a).rend() #define init(a, b) memset((a), (b), sizeof(a)) #define cpy(a, b) memcpy((a), (b), sizeof(a)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define size(x) (int)x.size() #define pb emplace_back #define mpr make_pair #define ls(i) ((i) << 1) #define rs(i) ((i) << 1 | 1) #define INF 0x3f3f3f3f #define NIF 0xc0c0c0c0 #define eps 1e-9 #define F first #define S second #define AC cin.tie(0)->sync_with_stdio(0) using namespace std; typedef long long llt; typedef __int128_t lll; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<llt, llt> pll; typedef complex<double> cd; // const int M = 998244353; // random_device rm; // mt19937 rg(rm()); // default_random_engine rg(rm()); // uniform_int_distribution<int> rd(INT_MIN, INT_MAX); // uniform_real_distribution<double> rd(0, M_PI); void db() { cerr << "\n"; } template <class T, class... U> void db(T a, U... b) { cerr << a << " ", db(b...); } inline char gc() { const static int SZ = 1 << 16; static char buf[SZ], *p1, *p2; if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2)) return -1; return *p1++; } void rd() {} template <typename T, typename... U> void rd(T &x, U &...y) { x = 0; bool f = 0; char c = gc(); while (!isdigit(c)) f ^= !(c ^ 45), c = gc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); f && (x = -x), rd(y...); } template <typename T> void prt(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) prt(x / 10); putchar((x % 10) ^ 48); } const llt MX = 1ll << 60; const int N = 1e5 + 5; struct P { llt sum; int ans; vector<llt> lsm, rsm, lnd, rnd; vector<int> lnb, rnb; inline void ini(int v) { sum = v, ans = 1; lsm = rsm = vector<llt>(1, 0); lnd = rnd = vector<llt>(1, v); lnb = rnb = vector<int>(1, 0); } } tr[N << 1]; P operator+(P &l, P &r) { P p; int slr = size(l.rnd), srl = size(r.lnd); p.sum = l.sum + r.sum, p.ans = 0; p.lsm = l.lsm, p.rsm = r.rsm; p.lnd = l.lnd, p.rnd = r.rnd; p.lnb = l.lnb, p.rnb = r.rnb; for (int i = 0; i < srl; i++) if (r.lnd[i] > l.sum) p.lnd.pb(r.lnd[i] - l.sum), p.lsm.pb(r.lsm[i] + l.sum); p.lnb.resize(size(p.lnd), 0); if (size(p.lnd) > size(l.lnd)) p.lnb[size(l.lnd)] = l.ans; else p.ans += l.ans; for (int i = 0; i < slr; i++) if (l.rnd[i] > r.sum) p.rnd.pb(l.rnd[i] - r.sum), p.rsm.pb(l.rsm[i] + r.sum); p.rnb.resize(size(p.rnd), 0); if (size(p.rnd) > size(r.rnd)) p.rnb[size(r.rnd)] = r.ans; else p.ans += r.ans; l.rnb.pb(0), l.rnd.pb(MX), l.rsm.pb(l.sum); r.lnb.pb(0), r.lnd.pb(MX), r.lsm.pb(r.sum); llt vl = 0; int num = 0; for (int i = 1, j = 0, p1 = 0; i <= slr; i++) { num += l.rnb[i]; // db(i, l.rnb[i], "qsdihqiwd"); while (l.rsm[i] >= r.lnd[j]) vl = r.lsm[++j]; if (vl < l.rnd[i]) { if (j == srl) { if (i == slr) p.ans += num; else { while (p.rsm[p1] < l.rsm[i] + r.sum) p1++; p.rnb[p1] += num; } } else if (i == slr) p.lnb[lower_bound(iter(p.lsm), r.lsm[j]) - p.lsm.begin()] += num; num = 0; } } vl = num = 0; for (int i = 1, j = 0, p2 = 0; i <= srl; i++) { num += r.lnb[i]; while (r.lsm[i] >= l.rnd[j]) vl = l.rsm[++j]; if (vl < r.lnd[i]) { if (j == slr) { if (i == srl) p.ans += num; else { while (p.lsm[p2] < r.lsm[i] + l.sum) p2++; p.lnb[p2] += num; } } else if (i == srl) p.rnb[lower_bound(iter(p.rsm), l.rsm[j]) - p.rsm.begin()] += num; num = 0; } } l.rnb.pop_back(), l.rnd.pop_back(), l.rsm.pop_back(); r.lnb.pop_back(), r.lnd.pop_back(), r.lsm.pop_back(); return p; } signed main() { int n, q, x, a, b; rd(n); auto pul = [&](int i) -> void { tr[i] = tr[ls(i)] + tr[rs(i)]; }; auto cg = [&](int p, int v) -> void { p += n - 1, tr[p].ini(v); for (p >>= 1; p; p >>= 1) pul(p); }; auto qy = [&](int l, int r) -> int { l += n - 1, r += n - 1; if (l == r) return tr[l].ans; // P pp = tr[l++]; // for (; l <= r; l++) // pp = pp + tr[l]; // return pp.ans; P p1 = tr[l++], p2 = tr[r--]; for (; l <= r; l >>= 1, r >>= 1) { if (l & 1) p1 = p1 + tr[l++]; if (~r & 1) p2 = tr[r--] + p2; } return (p1 + p2).ans; }; // for (int i = 1; i < n; i++) // { // tr[i] = tr[i - 1] + tr[i], db(tr[i].ans, tr[i].sum); // for (int p : tr[i].rnb) // cerr << p << ' '; // cerr << '\n'; // for (int p : tr[i].rsm) // cerr << p << ' '; // cerr << '\n'; // } for (int i = 0; i < n; i++) rd(x), tr[i + n].ini(x); for (int i = n - 1; i > 0; i--) pul(i); rd(q); while (q--) { rd(x, a, b); if (x == 1) cg(a, b); else prt(qy(a, b)), putchar('\n'); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...