Submission #616828

#TimeUsernameProblemLanguageResultExecution timeMemory
616828cheissmartFish 2 (JOI22_fish2)C++14
60 / 100
4070 ms517744 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]; char 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 { template<class A, class B> struct DS { pair<A, B> a[32]; int sz; DS() { sz = 0; } void clear() { sz = 0; } void EB(A x, B y) { a[sz++] = {x, y}; } void PB(pair<A, B> p) { a[sz++] = p; } pair<A, B>& operator[](int i) { return a[i]; } void resize(int s) { sz = s; } }; struct node { DS<int, ll> bad_pref, bad_suff; DS<int, int> bad_seg; ll sum; } t[N * 4]; void pull(int v, int posl = INF, int posr = 0) { for(int i = 0; i < t[v * 2].bad_pref.sz; i++) t[v].bad_pref.PB(t[v * 2].bad_pref[i]); for(int i = 0; i < t[v * 2 + 1].bad_suff.sz; i++) t[v].bad_suff.PB(t[v * 2 + 1].bad_suff[i]); for(int i = 0; i < t[v * 2 + 1].bad_pref.sz; i++) { // auto[pos1, sum1] = t[v * 2 + 1].bad_pref[i]; #define pos1 t[v * 2 + 1].bad_pref[i].F #define sum1 t[v * 2 + 1].bad_pref[i].S if(sum1 + t[v * 2].sum < a[pos1 + 1]) t[v].bad_pref.EB(pos1, sum1 + t[v * 2].sum); #undef pos1 #undef sum1 } for(int i = 0; i < t[v * 2].bad_suff.sz; i++) { // auto[pos1, sum1] = t[v * 2].bad_suff[i]; #define pos1 t[v * 2].bad_suff[i].F #define sum1 t[v * 2].bad_suff[i].S if(sum1 + t[v * 2 + 1].sum < a[pos1 - 1]) t[v].bad_suff.EB(pos1, sum1 + t[v * 2 + 1].sum); #undef pos1 #undef sum1 } int szi = t[v * 2].bad_suff.sz; int szj = t[v * 2 + 1].bad_pref.sz; 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) { int j = 0; for(int i = 0; i < t[v].bad_seg.sz; i++) { auto [l, r] = t[v].bad_seg[i]; if(r < pos - 1 || l > pos + 1) { t[v].bad_seg[j++] = t[v].bad_seg[i]; } else { cover::add(l, r + 1, -1); } } t[v].bad_seg.resize(j); 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::upd(int, int, int, int)':
fish2.cpp:139:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |    auto [l, r] = t[v].bad_seg[i];
      |         ^
#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...