Submission #702859

#TimeUsernameProblemLanguageResultExecution timeMemory
702859NursikWeirdtree (RMI21_weirdtree)C++14
5 / 100
66 ms9532 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 = 1e5 + 200, maxm = 1e4 + 200, inf = 1e9; int n; ll t[maxn * 4]; pair<ll, ll> tmx[maxn * 4]; void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){ if (tl == tr){ t[v] += val; tmx[v].s = tl; tmx[v].f += val; 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); } t[v] = t[v + v] + t[v + v + 1]; if (tmx[v + v].f == tmx[v + v + 1].f){ tmx[v].f = tmx[v + v].f, tmx[v].s = min(tmx[v + v].s, tmx[v + v + 1].s); } else{ tmx[v] = max(tmx[v + v], tmx[v + v + 1]); } // cout << tl << " " << tr << " " << t[v] << '\n'; } ll get(int l, int r, int v = 1, int tl = 1, int tr = n){ if (l <= tl && tr <= r){ return t[v]; } if (l > tr || r < tl) return 0; int tm = (tl + tr) / 2; return get(l, r, v + v, tl, tm) + get(l, r, v + v + 1, tm + 1, tr); } pair<ll, ll> getmx(int l, int r, int v = 1, int tl = 1, int tr = n){ if (l <= tl && tr <= r){ return tmx[v]; } if (l > tr || r < tl) return mp(0, 0); int tm = (tl + tr) / 2; return max(getmx(l, r, v + v, tl, tm), getmx(l, r, v + v + 1, tm + 1, tr)); } void initialise(int N, int Q, int h[]) { // Your code here. n = N; for (int i = 1; i <= n; ++i){ upd(i, h[i]); // exit(0); } // cout << get(1, 1) << " " << get(2, 2) << '\n'; } void cut(int l, int r, int k) { if (k == 1){ pair<ll, ll> cur = getmx(l, r); int pos = cur.s; if (cur.f > 0){ upd(pos, -1); } } } void magic(int i, int x) { // Your code here. ll val = get(i, i); upd(i, x - val); } long long int inspect(int l, int r) { // Your code here. return get(l, r); }
#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...