Submission #616513

#TimeUsernameProblemLanguageResultExecution timeMemory
616513cheissmartFish 2 (JOI22_fish2)C++14
60 / 100
4034 ms55352 KiB
// 花啊啊啊啊啊啊啊啊啊啊啊啊 #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0); #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; const int INF = 1e9 + 7, N = 1e5 + 7; const ll oo = 1e18; ll a[N]; int n; namespace cover { int t[N * 4], tag[N * 4]; int sum(int v, int len) { return tag[v] ? len : t[v]; } void _add(int l, int r, int x, int v = 1, int tl = 1, int tr = n + 1) { if(l <= tl && tr <= r) { tag[v] += x; return; } int tm = (tl + tr) / 2; if(l < tm) _add(l, r, x, v * 2, tl, tm); if(r > tm) _add(l, r, x, v * 2 + 1, tm, tr); t[v] = sum(v * 2, tm - tl) + sum(v * 2 + 1, tr - tm); } void add(int l, int r, int x) { if(l == 1 && r == n + 1) return; _add(l, r, x); } int qry(int l, int r, int v = 1, int tl = 1, int tr = n + 1) { if(l <= tl && tr <= r) return sum(v, tr - tl); int tm = (tl + tr) / 2, res = 0; if(l < tm) res += qry(l, r, v * 2, tl, tm); if(r > tm) res += qry(l, r, v * 2 + 1, tm, tr); return res; } } namespace seg { struct node { V<pair<int, ll>> bad_pref, bad_suff; V<pi> bad_seg; ll sum; } t[N * 4]; void pull(int v, int posl = INF, int posr = 0) { t[v].bad_pref = t[v * 2].bad_pref; t[v].bad_suff = t[v * 2 + 1].bad_suff; for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1]) t[v].bad_pref.EB(pos, sum + t[v * 2].sum); for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1]) t[v].bad_suff.EB(pos, sum + t[v * 2 + 1].sum); int szi = SZ(t[v * 2].bad_suff); int szj = SZ(t[v * 2 + 1].bad_pref); int i = 0, j = 0; while(i < szi && t[v * 2].bad_suff[i].F > posl) i++; while(j < szj && t[v * 2 + 1].bad_pref[j].F < posr) j++; while(i < szi && j < szj) { auto& he = t[v * 2].bad_suff[i], be = t[v * 2 + 1].bad_pref[j]; if(he.S + be.S < min(a[he.F - 1], a[be.F + 1])) { t[v].bad_seg.EB(he.F, be.F); cover::add(he.F, be.F + 1, 1); } if(a[he.F - 1] < a[be.F + 1]) i++; else j++; } t[v].sum = t[v * 2].sum + t[v * 2 + 1].sum; } void build(int v = 1, int tl = 1, int tr = n + 1) { if(tr - tl == 1) { t[v].sum = a[tl]; if(a[tl] < a[tl + 1]) t[v].bad_pref.EB(tl, a[tl]); if(a[tl] < a[tl - 1]) t[v].bad_suff.EB(tl, a[tl]); if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) { t[v].bad_seg.EB(tl, tl); cover::add(tl, tl + 1, 1); } } else { int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm, tr); pull(v); } } void upd(int pos, int v = 1, int tl = 1, int tr = n + 1) { V<pi> tt; for(auto[l, r]:t[v].bad_seg) { if(r < pos - 1 || l > pos + 1) { tt.EB(l, r); continue; } cover::add(l, r + 1, -1); } t[v].bad_seg = tt, t[v].bad_pref.clear(), t[v].bad_suff.clear(); if(tr - tl == 1) { t[v].sum = a[tl]; if(a[tl] < a[tl + 1]) t[v].bad_pref.EB(tl, a[tl]); if(a[tl] < a[tl - 1]) t[v].bad_suff.EB(tl, a[tl]); if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) { t[v].bad_seg.EB(tl, tl); cover::add(tl, tl + 1, 1); } } else { int tm = (tl + tr) / 2; if(pos - 1 < tm) upd(pos, v * 2, tl, tm); if(pos + 1 >= tm) upd(pos, v * 2 + 1, tm, tr); pull(v, pos + 1, pos - 1); } } } void upd(int pos, ll val) { a[pos] = val; seg::upd(pos); } signed main() { IO_OP; cin >> n; a[0] = a[n + 1] = oo; for(int i = 1; i <= n; i++) cin >> a[i]; seg::build(); int q; cin >> q; while(q--) { int op; cin >> op; if(op == 1) { int x, y; cin >> x >> y; upd(x, y); } else { int l, r; cin >> l >> r; ll tl = a[l - 1], tr = a[r + 1]; if(l - 1 >= 1) upd(l - 1, 1e15); if(r + 1 <= n) upd(r + 1, 1e15); if(l != 1 || r != n) cover::add(l, r + 1, -1); cout << r - l + 1 - cover::qry(l, r + 1) << '\n'; if(l != 1 || r != n) cover::add(l, r + 1, 1); if(l - 1 >= 1) upd(l - 1, tl); if(r + 1 <= n) upd(r + 1, tr); } } }

Compilation message (stderr)

fish2.cpp: In function 'void seg::pull(int, int, int)':
fish2.cpp:65:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
      |           ^
fish2.cpp:67:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |   for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1])
      |           ^
fish2.cpp: In function 'void seg::upd(int, int, int, int)':
fish2.cpp:110:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   for(auto[l, r]:t[v].bad_seg) {
      |           ^
#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...