Submission #703677

#TimeUsernameProblemLanguageResultExecution timeMemory
703677NursikWeirdtree (RMI21_weirdtree)C++14
0 / 100
241 ms36940 KiB
#include "weirdtree.h" #include <iostream> #include <fstream> #include <iomanip> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <unordered_set> #include <unordered_map> #include <stdio.h> #include <bitset> #include <cstdint> #include <cassert> #include <functional> #include <complex> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define f first #define s second const int maxn = 3e5 + 200, maxm = 1e4 + 200, inf = 1e9; int n; struct node{ ll sum = 0; ll max1 = 0; ll max2 = 0; ll fr = 0; } t[maxn * 4]; ll mv[maxn * 4]; node merge(node a, node b){ node c; c.sum = a.sum + b.sum; c.max1 = max(a.max1, b.max1); if (a.max1 == b.max1){ c.fr = a.fr + b.fr; c.max2 = max(a.max2, b.max2); } else{ if (a.max1 > b.max1){ c.fr = a.fr; c.max2 = max(a.max2, b.max1); } else{ c.fr = b.fr; c.max2 = max(b.max2, a.max1); } } return c; } void push(int v, int l, int r){ if (mv[v]){ if (l != r){ if (t[v + v].max1 == t[v].max1){ mv[v + v] += mv[v]; } if (t[v + v + 1].max1 == t[v].max1){ mv[v + v + 1] += mv[v]; } } t[v].sum += mv[v] * t[v].fr; t[v].max1 += mv[v]; mv[v] = 0; } } void upd(int pos, ll val, int v = 1, int tl = 1, int tr = n){ push(v, tl, tr); if (tl == tr){ t[v].sum = val; t[v].max1 = val; t[v].fr = 1; t[v].max2 = 0; return; } int tm = (tl + tr) / 2; if (pos <= tm){ upd(pos, val, v + v, tl, tm); } else{ upd(pos, val, v + v + 1, tm + 1, tr); } push(v + v, tl, tm); push(v + v + 1, tm + 1, tr); t[v] = merge(t[v + v], t[v + v + 1]); } node get(int l, int r, int v = 1, int tl = 1, int tr = n){ push(v, tl, tr); if (l <= tl && tr <= r){ return t[v]; } if (l > tr || r < tl){ node cl; cl.sum = 0; cl.max1 = 0; cl.max2 = 0; cl.fr = 0; return cl; } int tm = (tl + tr) / 2; return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr)); } void updlr(int l, int r, ll x, ll mx, int v = 1, int tl = 1, int tr = n){ push(v, tl, tr); if (l > tr || r < tl || t[v].max1 < mx) return; if (l <= tl && tr <= r && t[v].max1 - x > t[v].max2 && t[v].max1 == mx){ mv[v] -= x; push(v, tl, tr); return; } if (tl == tr && t[v].max1 == mx){ mv[v] -= (x); push(v, tl, tr); return; } int tm = (tl + tr) / 2; updlr(l, r, x, mx, v + v, tl, tm); updlr(l, r, x, mx, v + v + 1, tm + 1, tr); t[v] = merge(t[v + v], t[v + v + 1]); } void updlr2(int l, int r, ll x, ll &y, ll mx, int v = 1, int tl = 1, int tr = n){ push(v, tl, tr); if (l > tr || r < tl || t[v].max1 < mx){ return; } if (l <= tl && tr <= r && t[v].max1 - x - (y > 0) > t[v].max2 && (y == 0 || y >= t[v].fr) && t[v].max1 == mx){ /* if (l == 2 && r == 2){ cout << t[v].sum << '\n'; }*/ mv[v] -= (x + (y > 0)); y = max(0ll, y - t[v].fr); push(v, tl, tr); /*if (l == 2 && r == 2){ cout << t[v].sum << '\n'; }*/ return; } if (tl == tr && t[v].max1 == mx && (y == 0 || y >= t[v].fr)){ mv[v] -= (x + (y > 0)); y = max(0ll, y - t[v].fr); push(v, tl, tr); return; } int tm = (tl + tr) / 2; updlr2(l, r, x, y, mx, v + v, tl, tm); updlr2(l, r, x, y, mx, v + v + 1, tm + 1, tr); t[v] = merge(t[v + v], t[v + v + 1]); /*if (l == 2 && r == 2){ cout << v << " " << tl << " " << tr << " " << t[v].sum << '\n'; cout << x << '\n'; if (tl == 1 && tr == 2){ cout << t[v + v].sum << " " << t[v + v + 1].sum << '\n'; } }*/ } ll gets(int l, int r, int v = 1, int tl = 1, int tr = n){ push(v, tl, tr); if (l <= tl && tr <= r) return t[v].sum; if (l > tr || r < tl) return 0; int tm = (tl + tr) / 2; return gets(l, r, v + v, tl, tm) + gets(l, r, v + v + 1, tm + 1, tr); } void initialise(int N, int Q, int h[]) { n = N; for (int i = 1; i <= n; ++i){ upd(i, h[i]); } } void cut(int l, int r, int k) { while (k > 0){ node cur = get(l, r); if (cur.max1 == 0){ break; } ll rz = cur.max1 - cur.max2; if (rz * cur.fr <= k){ updlr(l, r, rz, cur.max1); k -= rz * cur.fr; } else{ ll all = rz * cur.fr; ll is = k % cur.fr; updlr2(l, r, k / cur.fr, is, cur.max1); k = 0; break; } } } void magic(int i, int x) { upd(i, x); } long long int inspect(int l, int r) { // Your code here. return gets(l, r); }

Compilation message (stderr)

weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:203:16: warning: unused variable 'all' [-Wunused-variable]
  203 |             ll all = rz * cur.fr;
      |                ^~~
#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...