Submission #622379

#TimeUsernameProblemLanguageResultExecution timeMemory
622379dooompyWeirdtree (RMI21_weirdtree)C++17
5 / 100
124 ms46672 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct node { ll max, smax, freqmax; ll sum; }; ll t[300005]; node combine(node a, node b) { if (a.max == b.max) { return {a.max, max(a.smax, b.smax), a.freqmax + b.freqmax, a.sum + b.sum}; } if (a.max < b.max) { return {b.max, max(a.max, b.smax), b.freqmax, a.sum + b.sum}; } else { return {a.max, max(a.smax, b.max), a.freqmax, a.sum + b.sum}; } } node tree[300005 * 4]; ll cutoff[300005 * 4]; void reset(ll x) { cutoff[x] = 1e15; } void pushdown(ll x, ll l, ll r) { // // // cout << x << " " << l << " " << r << " " << cutoff[x] << " " << tree[x].max; if (cutoff[x] >= tree[x].max) { reset(x); return; } if (l == r) { tree[x] = {cutoff[x], 0, 1, cutoff[x]}; reset(x); return; } if (cutoff[x] > tree[x].smax) { // // cout << tree[x].freqmax << " " << tree[x].max << " " << cutoff[x] << endl; tree[x].sum -= (tree[x].freqmax * (tree[x].max - cutoff[x])); tree[x].max = cutoff[x]; // // cout << "yes " << tree[x].sum << endl; } cutoff[2 * x] = min(cutoff[2 * x], cutoff[x]); cutoff[ 2 * x + 1] = min(cutoff[ 2 * x + 1], cutoff[x]); reset(x); } void build(ll x, ll l, ll r) { reset(x); if (l == r) { tree[x] = {t[l], 0, 1, t[l]}; // // // cout << t[l] << endl; // // // cout << tree[x].max << " " << tree[x].freqmax << " " << l << endl; // // // cout << "sum " << l << " " << tree[x].sum << endl; return; } ll mid = (l + r) /2; build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); tree[x] = combine(tree[2 * x], tree[2 * x + 1]); // // // cout << l << " " << r << " " << tree[x].sum << endl; } ll n; void initialise(int N, int q, int h[]) { for (ll i = 1; i <= N; i++) { t[i] = h[i]; // // // cout << t[i] << " asd " << endl; } n = N; // // cout << "llialise " << endl; build(1, 1, n); } pair<ll, ll> combpair(pair<ll, ll> a, pair<ll, ll> b) { if (a.first == b.first) { return {a.first, a.second + b.second}; } if (a.first > b.first) { return a; } else return b; } pair<ll, ll> getMaxInfo(ll x, ll l, ll r, ll ql, ll qr) { pushdown(x, l, r); if (ql <= l && r <= qr) return {tree[x].max, tree[x].freqmax}; if (l > qr || r < ql) return {0, 0}; ll mid = (l + r) / 2; return combpair(getMaxInfo(2 * x, l, mid, ql, qr), getMaxInfo(2 * x + 1, mid + 1, r, ql, qr)); } ll getSecondMax(ll x, ll l, ll r, ll ql, ll qr) { pushdown(x, l, r); if (ql <= l && r <= qr) return tree[x].smax; if (l > qr || r < ql) return 0; ll mid = (l + r) / 2; return max(getSecondMax(2 * x, l, mid, ql, qr), getSecondMax(2 * x + 1, mid + 1, r, ql, qr)); } ll getSum(ll x, ll l, ll r, ll ql, ll qr) { pushdown(x, l, r); if (ql <= l && r <= qr) return tree[x].sum; if (l > qr || r < ql) return 0; ll mid = (l + r) / 2; ll a = getSum(2 * x, l, mid, ql, qr); ll b = getSum(2 * x + 1, mid + 1, r, ql, qr); tree[x] = combine(tree[2 * x], tree[2 * x + 1]); return a + b; } void lazy(ll x, ll l, ll r, ll ql, ll qr, ll lazyval) { // // cout << ql << " " << qr << " " << lazyval << endl; pushdown(x, l, r); if (ql > r || qr < l || lazyval > tree[x].max) return; if ((ql <= l && r <= qr && lazyval > tree[x].smax) || (l == r)) { cutoff[x] = lazyval; // // cout << "asdf " << l << " " << r << " " << lazyval << endl; // cout << tree[x].sum << endl; pushdown(x, l, r); // cout << tree[x].sum << endl; return; } # warning may need to fix ll mid = (l + r) / 2; lazy(2 * x, l, mid, ql, qr, lazyval); lazy(2 * x + 1, mid + 1, r, ql, qr, lazyval); tree[x] = combine(tree[2 * x], tree[2 * x + 1]); } ll walkdown(ll x, ll l, ll r, ll ql, ll qr, ll ct, ll maxcomp) { pushdown(x, l, r); if (tree[x].max < maxcomp) return 0; if (l == r) { return l; } ll mid = (l + r) / 2; if (tree[2 * x].max == maxcomp && ct >= tree[2 * x].freqmax) { ct -= tree[2 * x].freqmax; return walkdown(x, mid + 1, r, ql, qr, ct, maxcomp); } else if (tree[2 * x].max == maxcomp & ct < tree[2 * x].freqmax) { return walkdown(2 * x, l, mid, ql, qr, ct, maxcomp); } else { return walkdown(2 * x + 1, mid + 1, r, ql, qr, ct, maxcomp); } } void cut(int l, int r, int k) { // // // cout << "firts seen " << endl; // return; while (k >= 0) { auto maxinfo = getMaxInfo(1, 1, n, l, r); ll smax = getSecondMax(1, 1, n, l, r); if (maxinfo.first == 0) return; ll curavail = (maxinfo.first - smax) * maxinfo.second; if (k < curavail) { // need to split it somewhere ll lvls = k / maxinfo.second; ll remains = k % maxinfo.second; // cout << "bruh" << endl; // cout << lvls << " " << remains << endl; if (remains == 0) { // // cout << "asdf " << maxinfo.first - lvls << endl; lazy(1, 1, n, l, r, maxinfo.first - lvls); } else { k = 0; ll idx = walkdown(1, 1, n, l, r, remains, maxinfo.first); lazy(1, 1, n, l, idx, maxinfo.first - lvls - 1); if (idx > r) { k = 0; break; } lazy(1, 1, n, idx + 1, r, maxinfo.first - lvls); } k = 0; break; } else { lazy(1, 1, n, l, r, smax); k -= curavail; } } return; // // // cout << "cutdown " << endl; } void setbruh(ll x, ll l, ll r, ll i, ll xx) { pushdown(x, l, r); if (l == r) { tree[x] = {xx, 0, 1, xx}; return; } ll mid = (l + r) / 2; if (i <= mid) setbruh(2 * x, l, mid, i, xx); else setbruh(2 * x + 1, mid + 1, r, i, xx); pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r); // // cout << l << " " << r << endl; // // cout << tree[2 * x].max << " " << tree[2 * x + 1].max << endl; tree[x] = combine(tree[2 * x], tree[2 * x + 1]); // // cout << tree[x].max << " " << tree[x].smax << " " << l << " " << r << endl; } void magic(int i, int x ) { // // cout << "magic " << endl; setbruh(1, 1, n, i, x); } ll inspect(int l, int r) { // // cout << "inspect " << endl; return getSum(1, 1, n, l, r); }

Compilation message (stderr)

weirdtree.cpp:166:3: warning: #warning may need to fix [-Wcpp]
  166 | # warning may need to fix
      |   ^~~~~~~
weirdtree.cpp: In function 'll walkdown(ll, ll, ll, ll, ll, ll, ll)':
weirdtree.cpp:190:32: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  190 |     } else if (tree[2 * x].max == maxcomp & ct < tree[2 * x].freqmax) {
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~
#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...