Submission #887297

#TimeUsernameProblemLanguageResultExecution timeMemory
887297alex_2008Monkey and Apple-trees (IZhO12_apple)C++14
100 / 100
283 ms73908 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cmath> #include <iomanip> #include <algorithm> #include <vector> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <fstream> #include <bitset> typedef long long ll; using namespace std; const int N = 1e7 + 10; int sz = 1; int lazy[N]; int sm[N]; int l[N]; int r[N]; void update(int v, int tl, int tr, int ql, int qr) { if (tl > qr || tr < ql) { return; } if (tl >= ql && tr <= qr) { sm[v] = (tr - tl + 1); lazy[v] = 1; return; } if (!l[v]) l[v] = ++sz; if (!r[v]) r[v] = ++sz; int tm = (tl + tr) / 2; if (lazy[v]) { lazy[l[v]] = 1; sm[l[v]] = (tm - tl + 1); lazy[r[v]] = 1; sm[r[v]] = (tr - tm); lazy[v] = 0; } update(l[v], tl, tm, ql, qr); update(r[v], tm + 1, tr, ql, qr); sm[v] = sm[l[v]] + sm[r[v]]; } int sum(int v, int tl, int tr, int ql, int qr) { if (tr < ql || tl > qr) return 0; if (tl >= ql && tr <= qr) { return sm[v]; } if (!l[v]) l[v] = ++sz; if (!r[v]) r[v] = ++sz; int tm = (tl + tr) / 2; if (lazy[v]) { lazy[l[v]] = 1; sm[l[v]] = (tm - tl + 1); lazy[r[v]] = 1; sm[r[v]] = (tr - tm); lazy[v] = 0; } return sum(l[v], tl, tm, ql, qr) + sum(r[v], tm + 1, tr, ql, qr); } int main() { int m, c = 0; cin >> m; for (int i = 1; i <= m; i++) { int d, x, y; cin >> d >> x >> y; if (d == 2) { update(1, 1, 1e9, x + c, y + c); } else { c = sum(1, 1, 1e9, x + c, y + c); cout << c << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...