Submission #786687

#TimeUsernameProblemLanguageResultExecution timeMemory
786687flappybirdWeirdtree (RMI21_weirdtree)C++17
10 / 100
236 ms77052 KiB
#include "weirdtree.h" #include <bits/stdc++.h> using namespace std; #define MAX 301010 typedef long long ll; struct node { ll sum; ll mx; ll cnt; ll mx2; node(ll x) { sum = mx = x; cnt = 1; mx2 = -1; } node() { cnt = -1; sum = 0; mx = mx2 = 0; } }; node operator+(node n1, node n2) { if (!~n1.cnt) return n2; if (!~n2.cnt) return n1; node ret; ret.sum = n1.sum + n2.sum; ret.mx = max(n1.mx, n2.mx); ret.mx2 = max(n1.mx2, n2.mx2); if (n1.mx != n2.mx) ret.mx2 = max(ret.mx2, min(n1.mx, n2.mx)); ret.cnt = 0; if (ret.mx == n1.mx) ret.cnt += n1.cnt; if (ret.mx == n2.mx) ret.cnt += n2.cnt; return ret; } node tree[MAX * 4]; ll lazy[MAX * 4]; ll H[MAX]; int N; void init(int s, int e, int loc = 1) { lazy[loc] = 1e18; if (s == e) { tree[loc] = node(H[s]); return; } int m = s + e >> 1; init(s, m, loc * 2); init(m + 1, e, loc * 2 + 1); tree[loc] = tree[loc * 2] + tree[loc * 2 + 1]; } void prop(int loc) { for (auto c : { loc * 2, loc * 2 + 1 }) { ll d = tree[c].mx - lazy[loc]; tree[c].mx = min(tree[c].mx, lazy[loc]); if (d < 0) d = 0; tree[c].sum -= 1ll * d * tree[c].cnt; lazy[c] = min(lazy[c], lazy[loc]); } lazy[loc] = 1e18; } void upd(int s, int e, int i, ll x, int loc = 1) { if (e < i || i < s) return; if (s != e) prop(loc); if (s == e) { tree[loc] = node(x); return; } int m = s + e >> 1; upd(s, m, i, x, loc * 2); upd(m + 1, e, i, x, loc * 2 + 1); tree[loc] = tree[loc * 2] + tree[loc * 2 + 1]; } void upd(int i, ll x) { upd(1, N, i, x); } void down(int s, int e, int l, int r, ll x, int loc = 1) { if (e < l || r < s) return; if (s != e) prop(loc); int c = 0; if (l <= s && e <= r) { lazy[loc] = min(lazy[loc], x); c = 1; if (tree[loc].mx <= x) return; else if (tree[loc].mx2 < x) { tree[loc].sum -= 1ll * (tree[loc].mx - x) * tree[loc].cnt; tree[loc].mx = x; return; } c = 0; } if (!c) { int m = s + e >> 1; down(s, m, l, r, x, loc * 2); down(m + 1, e, l, r, x, loc * 2 + 1); tree[loc] = tree[loc * 2] + tree[loc * 2 + 1]; } } void down(int l, int r, ll x) { down(1, N, l, r, x); } node query(int s, int e, int l, int r, int loc = 1) { if (e < l || r < s) return node(); if (s != e) prop(loc); if (l <= s && e <= r) return tree[loc]; int m = s + e >> 1; return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1); } node query(int l, int r) { return query(1, N, l, r); } int mxcount(int s, int e, int l, int r, ll x, int k, int loc = 1) { if (e < l || r < s) return -1; if (s != e) prop(loc); if (l <= s && e <= r) { if (x == tree[loc].mx) { if (tree[loc].cnt < k) return -1; if (s == e) return s; int m = s + e >> 1; if (tree[loc * 2].mx == x && tree[loc * 2].cnt >= k) return mxcount(s, m, l, r, x, k, loc * 2); else return mxcount(m + 1, e, l, r, x, k - tree[loc * 2].cnt, loc * 2 + 1); } else return -1; } int m = s + e >> 1; int res = mxcount(s, m, l, r, x, k, loc * 2); if (~res) return res; auto q = query(s, m, l, r, loc * 2); return mxcount(m + 1, e, l, r, x, k - q.cnt, loc * 2 + 1); } int mxcount(int l, int r, ll x, int k) { return mxcount(1, N, l, r, x, k); } void initialise(int N, int Q, int h[]) { ::N = N; int i; for (i = 1; i <= N; i++) H[i] = h[i]; init(1, N); } void cut(int l, int r, int k) { while (k) { auto res = query(l, r); if (res.mx == 0) return; if (res.cnt >= k) { int ind = mxcount(l, r, res.mx, k); down(l, ind, res.mx - 1); break; } ll rem = res.mx - max(0ll, res.mx2); rem *= res.cnt; ll m = min(k / res.cnt, res.mx - res.mx2); down(l, r, res.mx - m); k -= m * res.cnt; } } void magic(int i, int x) { upd(i, x); } long long int inspect(int l, int r) { return query(l, r).sum; }

Compilation message (stderr)

weirdtree.cpp: In function 'void init(int, int, int)':
weirdtree.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void upd(int, int, int, ll, int)':
weirdtree.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'void down(int, int, int, int, ll, int)':
weirdtree.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   int m = s + e >> 1;
      |           ~~^~~
weirdtree.cpp: In function 'node query(int, int, int, int, int)':
weirdtree.cpp:108:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |  int m = s + e >> 1;
      |          ~~^~~
weirdtree.cpp: In function 'int mxcount(int, int, int, int, ll, int, int)':
weirdtree.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |    int m = s + e >> 1;
      |            ~~^~~
weirdtree.cpp:126:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |  int m = s + e >> 1;
      |          ~~^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...