Submission #679526

#TimeUsernameProblemLanguageResultExecution timeMemory
679526elkernosFish 2 (JOI22_fish2)C++17
43 / 100
3131 ms16676 KiB
// while (clock()<=69*CLOCKS_PER_SEC) // #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("O3") // #pragma GCC target ("avx2") // #pragma GCC optimize("Ofast") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define sim template <class c #define ris return *this #define dor > debug &operator<< #define eni(x) \ sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \ { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c *x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef XOX ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair<b, c> d) { ris << "" << d.first << " --> " << d.second << ""; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c &) { ris; } #endif } ; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #ifdef XOX #warning Times may differ!!! #endif #define endl '\n' #define pb emplace_back #define vt vector #define rep(i, a, b) for (int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() 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 + 5, 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 { typedef ll T; static constexpr T unit = 0; T f(T a, T b) { return a + b; } // (any associative fn) vector<T> s; int n; Sum(int nd = nax, T def = unit) : s(2 * nd, def), n(nd) {} void update(int pos, T val) { for (s[pos += n] = val; pos /= 2;) s[pos] = f(s[pos * 2], s[pos * 2 + 1]); } T query(int b, int e) { T ra = unit, rb = unit; for (b += n, e += n + 1; b < e; b /= 2, e /= 2) { if (b % 2) ra = f(ra, s[b++]); if (e % 2) rb = f(s[--e], rb); } return f(ra, rb); } }; 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); CMin intervals; Sum getsum; Max getmax; cin >> n; 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})) { debug() << imie(l) imie(r) imie(x); alive.emplace(l, r); intervals.add(l + 1, r - 1, +1); } } if (x == -1) { if (alive.count({l, r})) { debug() << imie(l) imie(r) imie(x); 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...