Submission #1304438

#TimeUsernameProblemLanguageResultExecution timeMemory
1304438muhammad-ahmadMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
490 ms263672 KiB
#include<bits/stdc++.h> using namespace std; #define int long long struct node { int left = -1; int right = -1; int sum = 0; int lazy = 0; }; int cur; vector<node> tree; void apply(int v, int len, int val){ if (val == 1){ tree[v].lazy = val; tree[v].sum = len * val; } } int merge(int a, int b){ return (a + b); } void push(int v, int s, int e){ int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2; if (lc == -1){ tree[v].left = ++cur; tree.push_back(node()); } if (rc == -1){ tree[v].right = ++cur; tree.push_back(node()); } apply(tree[v].left, mid - s, tree[v].lazy); apply(tree[v].right, e - mid, tree[v].lazy); tree[v].lazy = 0; } void upd(int val, int l, int r, int v = 0, int s = 0, int e = 1e9 + 5){ if (e <= l or r <= s) return; if (l <= s && e <= r){ apply(v, e - s, val); return; } push(v, s, e); int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2; upd(val, l, r, lc, s, mid); upd(val, l, r, rc, mid, e); tree[v].sum = merge(tree[lc].sum, tree[rc].sum); } int sum(int l, int r, int v = 0, int s = 0, int e = 1e9 + 5){ if (e <= l or r <= s) return 0; if (l <= s && e <= r) return tree[v].sum; push(v, s, e); int lc = tree[v].left, rc = tree[v].right, mid = (s + e) / 2; return merge(sum(l, r, lc, s, mid), sum(l, r, rc, mid, e)); } signed main(){ int m; cin >> m; tree.push_back(node()); int c = 0; for (int i = 1; i <= m; i++){ int t; cin >> t; int l, r; cin >> l >> r; r++; l += c, r += c; if (t == 1){ c = sum(l, r); cout << c << endl; } else { upd(1, l, r); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...