Submission #888921

#TimeUsernameProblemLanguageResultExecution timeMemory
888921chuongdanMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
1287 ms262144 KiB
#include <bits/stdc++.h> #define N 100000 #define fi first #define se second #define pb push_back #define mp make_pair #define int long long #define rep(i, l, r) for(int i = l; i <= r; i++) using namespace std; typedef string str; typedef pair<int,int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iv; const int inf = 1e9; const int MOD = 1e9 + 7; const bool multi_test = false; const string NAME = "VOI"; struct node { int sum, lazy, tl, tr, l, r; node() : sum(0), lazy(0), l(-1), r(-1) {} }; struct sparse_segment_tree{ int cnt; node st[30*N+5]; void init(){ cnt = 1; st[cnt].tl = 1; st[cnt].tr = 1e9; } void down_lazy(int id){ if (st[id].lazy){ int mid = (st[id].tl + st[id].tr) / 2; if (st[id].l == -1){ st[id].l = ++cnt; st[cnt].tl = st[id].tl; st[cnt].tr = mid; } if (st[id].r == -1){ st[id].r = ++cnt; st[cnt].tl = mid + 1; st[cnt].tr = st[id].tr; } st[st[id].l].sum = mid - st[id].tl + 1; st[st[id].r].sum = st[id].tr - mid; st[st[id].l].lazy = st[st[id].r].lazy = 1; st[id].lazy = 0; } } void update(int u, int v, int id = 1){ int l = st[id].tl, r = st[id].tr; if (l > v || r < u) return; if (u <= l && r <= v) { st[id].sum = r - l + 1; st[id].lazy = 1; return; } int mid = (l + r) >> 1; down_lazy(id); if (st[id].l == -1){ st[id].l = ++cnt; st[cnt].tl = l; st[cnt].tr = mid; // cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl; } if (st[id].r == -1){ st[id].r = ++cnt; st[cnt].tl = mid + 1; st[cnt].tr = r; // cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl; } // cout << u << " " << v << " " << l << " " << r << " " << id << " " << st[id].l << " " << st[id].r << endl; update(u, v, st[id].l); update(u, v, st[id].r); st[id].sum = st[st[id].l].sum + st[st[id].r].sum; } int querry(int u, int v, int id = 1){ int l = st[id].tl, r = st[id].tr; if (l > v || r < u) return 0; if (u <= l && r <= v) return st[id].sum; int mid = (l + r) >> 1; down_lazy(id); if (st[id].l == -1){ st[id].l = ++cnt; st[cnt].tl = l; st[cnt].tr = mid; } if (st[id].r == -1){ st[id].r = ++cnt; st[cnt].tl = mid + 1; st[cnt].tr = r; } return querry(u, v, st[id].l) + querry(u, v, st[id].r); } }; int n; sparse_segment_tree st; void solve(){ cin >> n; st.init(); int c = 0; while (n--){ int d, x, y; cin >> d >> x >> y; if (d == 1) { c = st.querry(x + c, y + c); cout << c << '\n'; } else { st.update(x + c, y + c); } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; if (multi_test) cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...