Submission #679535

#TimeUsernameProblemLanguageResultExecution timeMemory
679535elkernosFish 2 (JOI22_fish2)C++17
48 / 100
4054 ms17140 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define pb emplace_back #define vt vector typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int nax = 100 * 1007; const ll oo = 1e17; int n; #define lc 2 * v #define rc 2 * v + 1 #define m (l + r) / 2 struct CMin { struct Node { pii p = {0, 1}; int lazy = 0; void dod(int x) { p.first += x; lazy += x; } }; Node nothing = {{n + 213, 0}, 0}; friend Node operator+(const Node &l, const Node &r) { Node ret; ret.p = min(l.p, r.p); if (l.p.first == r.p.first) ret.p.second = l.p.second + r.p.second; return ret; } Node tree[4 * nax]; void push(int v) { for (auto to : {lc, rc}) tree[to].dod(tree[v].lazy); tree[v].lazy = 0; } void build(int v = 1, int l = 0, int r = n + 1) { if (l == r) { tree[v].p.second = 1; return; } build(lc, l, m), build(rc, m + 1, r); tree[v] = tree[lc] + tree[rc]; } void add(int ql, int qr, int x, int v = 1, int l = 0, int r = n + 1) { if (r < ql || qr < l) return; if (ql <= l && r <= qr) { tree[v].dod(x); return; } push(v); add(ql, qr, x, lc, l, m), add(ql, qr, x, rc, m + 1, r); tree[v] = tree[lc] + tree[rc]; } Node query(int ql, int qr, int v = 1, int l = 0, int r = n + 1) { if (r < ql || qr < l) return nothing; if (ql <= l && r <= qr) return tree[v]; push(v); return query(ql, qr, lc, l, m) + query(ql, qr, rc, m + 1, r); } }; struct Sum { ll tree[4 * nax]; void update(int pos, ll to, int v = 1, int l = 0, int r = n + 1) { if (pos < l || r < pos) return; if (l == r) { tree[v] = to; return; } update(pos, to, lc, l, m), update(pos, to, rc, m + 1, r); tree[v] = tree[lc] + tree[rc]; } ll query(int ql, int qr, int v = 1, int l = 0, int r = n + 1) { if (r < ql || qr < l) return 0; if (ql <= l && r <= qr) return tree[v]; return query(ql, qr, lc, l, m) + query(ql, qr, rc, m + 1, r); } }; struct Max { ll tree[4 * nax]; void update(int pos, ll to, int v = 1, int l = 0, int r = n + 1) { if (pos < l || r < pos) return; if (l == r) { tree[v] = to; return; } update(pos, to, lc, l, m), update(pos, to, rc, m + 1, r); tree[v] = max(tree[lc], tree[rc]); } int maxPrawo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1) { if (tree[v] <= od) return -1; if (l == r) return l; if (ogr <= m) return maxPrawo(ogr, od, lc, l, m); int ret = maxPrawo(ogr, od, rc, m + 1, r); return ret != -1 ? ret : maxPrawo(ogr, od, lc, l, m); } int maxLewo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1) { if (tree[v] <= od) return -1; if (l == r) return l; if (m < ogr) return maxLewo(ogr, od, rc, m + 1, r); int ret = maxLewo(ogr, od, lc, l, m); return ret != -1 ? ret : maxLewo(ogr, od, rc, m + 1, r); } }; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; CMin intervals; Sum getsum; Max getmax; vt<ll> a(n + 2); for (int i = 1; i <= n; i++) cin >> a[i]; a[0] = a[n + 1] = oo; for (int i = 0; i <= n + 1; i++) { getsum.update(i, a[i]); getmax.update(i, a[i]); } intervals.build(); set<pair<int, int>> alive; auto good = [&](int l, int r) { if (r - l + 1 <= 2) return false; return getsum.query(l + 1, r - 1) < min(a[l], a[r]); }; auto wsadz = [&](int l, int r, int x) { if (x == +1) { if (!alive.count({l, r})) { alive.emplace(l, r); intervals.add(l + 1, r - 1, +1); } } if (x == -1) { if (alive.count({l, r})) { alive.erase({l, r}); intervals.add(l + 1, r - 1, -1); } } }; auto wezL = [&](int l, int r) { return getmax.maxPrawo(l - 1, getsum.query(l, r - 1)); }; auto wezR = [&](int l, int r) { return getmax.maxLewo(r + 1, getsum.query(l + 1, r)); }; auto findboth = [&](int p, int x) { int l = p - 1, r = p + 1; while (1) { if (good(l, r)) wsadz(l, r, x); if (l == 0 && r == n + 1) break; if (a[l] < a[r]) l = wezL(l, r); else r = wezR(l, r); } }; auto findpresuf = [&](int p, int x) { int r = wezR(p, p); while (1) { if (good(p, r)) wsadz(p, r, x); if (r == n + 1) break; r = wezR(p, r); } int l = wezL(p, p); while (1) { if (good(l, p)) wsadz(l, p, x); if (l == 0) break; l = wezL(l, p); } }; for (int i = 1; i <= n; i++) { findboth(i, +1); findpresuf(i, +1); } int q; cin >> q; while (q--) { int type; cin >> type; if (type == 1) { int i, x; cin >> i >> x; findboth(i, -1); findpresuf(i, -1); a[i] = x; getsum.update(i, x); getmax.update(i, x); findboth(i, +1); findpresuf(i, +1); } else { int l, r; cin >> l >> r; int real_l = l, real_r = r; int lp = l + 1, rp = r - 1; while (lp <= r) { if (getsum.query(l, lp - 1) < a[lp]) real_l = lp; lp = wezR(l, lp); } while (l <= rp) { if (getsum.query(rp + 1, r) < a[rp]) real_r = rp; rp = wezL(rp, r); } cout << intervals.query(real_l, real_r).p.second << endl; } } }
#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...