Submission #1190780

#TimeUsernameProblemLanguageResultExecution timeMemory
1190780TheGreatAntivirusMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
1 ms320 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define stdI freopen("input.txt", "r", stdin); #define stdO freopen("output.txt", "w", stdout); #define all(x) x.begin(), x.end() #define mp(x, y) make_pair(x, y) #define int long long #define F first #define S second #ifdef OMAIN #include <tools/debug.h> #else #define dbg(...) #define ddbg(...) #endif using namespace std; using namespace __gnu_pbds; template<typename T, template<typename> class order = less> using ordered_set = tree<T, null_type, order<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef pair<int, int> pii; const int MAXN = 1 << 30, MAXLOG = 18, MAXSQ = 500, INF = 1e18, MOD = 1e9 + 7; struct segment { struct node { int q = 0, lzy = 0, lc = -1, rc = -1; }; vector<node> sg; int root; segment() { sg.emplace_back(); root = 0; } void push(int v, int vl, int vr) { if(sg[v].lzy != 0) { sg[v].q = sg[v].lzy; sg[v].lzy = 0; if(vl == vr) { return; } if(sg[v].lc == -1) { sg[v].lc = sg.size(); sg.emplace_back(); } if(sg[v].rc == -1) { sg[v].rc = sg.size(); sg.emplace_back(); } int val = (vr - vl + 1) >> 1; sg[sg[v].lc].lzy = sg[sg[v].rc].lzy = val; } } void update(int v, int vl, int vr, int l, int r) { push(v, vl, vr); if(vl > r || vr < l || v == -1) { return; } if(l <= vl && vr <= r) { sg[v].lzy = vr - vl + 1; push(v, vl, vr); return; } int mid = (vl + vr) >> 1; if(sg[v].lc == -1) { sg[v].lc = sg.size(); sg.emplace_back(); } if(sg[v].rc == -1) { sg[v].rc = sg.size(); sg.emplace_back(); } update(sg[v].lc, vl, mid, l, r); update(sg[v].rc, mid + 1, vr, l, r); int lq = sg[v].lc == -1 ? 0 : sg[sg[v].lc].q; int rq = sg[v].rc == -1 ? 0 : sg[sg[v].rc].q; sg[v].q = lq + rq; } int get(int v, int vl, int vr, int l, int r) { push(v, vl, vr); if(vl > r || vr < l || v == -1) { return 0; } if(l <= vl && vr <= r) { return sg[v].q; } int mid = (vl + vr) >> 1; return get(sg[v].lc, vl, mid, l, r) + get(sg[v].rc, mid + 1, vr, l, r); } } s; void solve() { int q, c = 0; cin >> q; while(q--) { int tp; cin >> tp; if(tp == 1) { int l, r; cin >> l >> r; l += c - 1; r += c - 1; c = s.get(0, 0, MAXN - 1, l, r); cout << c << "\n"; } else { int l, r; cin >> l >> r; l += c - 1; r += c - 1; s.update(0, 0, MAXN - 1, l, r); } } } int32_t main() { IOS; int t = 1; //cin >> t; while(t--) { solve(); } #ifdef OMAIN cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...