Submission #617433

#TimeUsernameProblemLanguageResultExecution timeMemory
617433cheissmartFish 2 (JOI22_fish2)C++14
60 / 100
4108 ms237580 KiB
// 花啊啊啊啊啊啊啊啊啊啊啊啊 #include <iostream> #include <cstring> #pragma GCC optimize("Ofast") #define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0); #define F first #define S second #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; const int INF = 1e9 + 7, N = 1e5 + 2; const ll oo = 1e16; ll a[N]; int n; namespace cover { int t[N * 2]; char tag[N * 2]; int sum(int v, int h) { return tag[v] ? (1 << h) : t[v]; } void pull(int p) { int h = 0; while(p > 1) { t[p >> 1] = sum(p, h) + sum(p ^ 1, h); p >>= 1; h++; } } void add(int l, int r, int x) { if(l == 1 && r == n + 1) return; l--, r--; int tl = l, tr = r; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) tag[l++] += x; if(r & 1) tag[--r] += x; } pull(tl + n), pull(tr - 1 + n); } int qry(int l, int r) { l--, r--; int res = 0, h = 0; for(l += n, r += n; l < r; l >>= 1, r >>= 1, h++) { if(l & 1) res += sum(l++, h); if(r & 1) res += sum(--r, h); } return res; } } namespace seg { template<class A, class B> struct DS { pair<A, B> a[29]; 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; } }; void cpy(DS<int, ll>& a, DS<int, ll>& b) { a.sz = b.sz; memcpy(a.a, b.a, a.sz * sizeof (a.a[0])); } struct node { DS<int, ll> bad_pref, bad_suff; DS<int, int> bad_seg; ll sum; } t[N * 2]; int id(int tl, int tr) { tl--, tr -= 2; return (tl + tr) | (tl != tr); } void pull(int v, int tl, int tr, int lc, int rc, int posl = INF, int posr = 0) { cpy(t[v].bad_pref, t[lc].bad_pref); cpy(t[v].bad_suff, t[rc].bad_suff); for(int i = 0; i < t[rc].bad_pref.sz; i++) { ll sum1 = t[rc].bad_pref[i].S + t[lc].sum; int pos1 = t[rc].bad_pref[i].F; if(sum1 + a[tl - 1] < a[pos1 + 1]) t[v].bad_pref.EB(pos1, sum1); } for(int i = 0; i < t[lc].bad_suff.sz; i++) { ll sum1 = t[lc].bad_suff[i].S + t[rc].sum; int pos1 = t[lc].bad_suff[i].F; if(sum1 + a[tr] < a[pos1 - 1]) t[v].bad_suff.EB(pos1, sum1); } int szi = t[lc].bad_suff.sz; int szj = t[rc].bad_pref.sz; int i = 0, j = 0; while(i < szi && t[lc].bad_suff[i].F > posl) i++; while(j < szj && t[rc].bad_pref[j].F < posr) j++; while(i < szi && j < szj) { auto& he = t[lc].bad_suff[i], be = t[rc].bad_pref[j]; if(a[he.F - 1] < a[be.F + 1]) { if(he.S + be.S < a[he.F - 1]) { t[v].bad_seg.EB(he.F, be.F); cover::add(he.F, be.F + 1, 1); } i++; } else { if(he.S + be.S < a[be.F + 1]) { t[v].bad_seg.EB(he.F, be.F); cover::add(he.F, be.F + 1, 1); } j++; } } t[v].sum = t[lc].sum + t[rc].sum; } void build(int tl = 1, int tr = n + 1) { int v = id(tl, tr); if(tr - tl == 1) { t[v].sum = a[tl]; if(a[tl] + a[tl - 1] < a[tl + 1]) t[v].bad_pref.EB(tl, a[tl]); if(a[tl] + a[tl + 1] < 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 + 1) / 2; build(tl, tm); build(tm, tr); pull(v, tl, tr, id(tl, tm), id(tm, tr)); } } void upd(int pos, int tl = 1, int tr = n + 1) { int v = id(tl, tr); 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] < a[tl + 1]) t[v].bad_pref.EB(tl, a[tl]); if(a[tl] + a[tl + 1] < 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 + 1) / 2; if(pos - 1 < tm) upd(pos, tl, tm); if(pos + 1 >= tm) upd(pos, tm, tr); pull(v, tl, tr, id(tl, tm), id(tm, tr), pos + 1, pos - 1); } } } void upd(int pos, ll val) { a[pos] = val; seg::upd(pos); } #define gc getchar_unlocked inline int readInt () { int c = gc(); while(!isdigit(c)) c = gc(); int res = c - '0'; while(isdigit(c = gc())) res = res * 10 + c - '0'; return res; } #define pc(x) putchar_unlocked(x); inline void writeInt (int n) { int N = n, rev, count = 0; rev = N; if (N == 0) { pc('0'); return ;} while ((rev % 10) == 0) { count++; rev /= 10;} rev = 0; while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;} while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;} while (count--) pc('0'); } signed main() { IO_OP; n = readInt(); a[0] = a[n + 1] = oo; for(int i = 1; i <= n; i++) a[i] = readInt(); seg::build(); int q = readInt(); while(q--) { int op = readInt(); if(op == 1) { int x = readInt(), y = readInt(); upd(x, y); } else { int l = readInt(), r = readInt(); 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); writeInt(r - l + 1 - cover::qry(l, r + 1)); pc('\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::cpy(seg::DS<int, long long int>&, seg::DS<int, long long int>&)':
fish2.cpp:71:42: warning: 'void* memcpy(void*, const void*, size_t)' writing to an object of type 'struct std::pair<int, long long int>' with no trivial copy-assignment; use copy-assignment or copy-initialization instead [-Wclass-memaccess]
   71 |   memcpy(a.a, b.a, a.sz * sizeof (a.a[0]));
      |                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fish2.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
fish2.cpp: In function 'void seg::upd(int, int, int)':
fish2.cpp:148:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |    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...