Submission #1276332

#TimeUsernameProblemLanguageResultExecution timeMemory
1276332ayazMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
131 ms300864 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> const int MXN = 2e5+5; const ll mod = 1e9+7; struct SegTree { struct node { int li=0, ri=0, lz=0; ll res=0; }; vector<node> st; int n, last=1; void init(int _n) { n = _n; st.resize(n*4*32); } void create(int v) { if (st[v].li) return; st[v].li = ++last; st[v].ri = ++last; } void relax(int l, int r, int v) { if (!st[v].lz) return; st[v].res = (r-l+1); if (l != r) { create(v); st[st[v].li].lz = 1; st[st[v].ri].lz = 1; } st[v].lz = 0; } void update(int ql, int qr, int l, int r, int v) { if (qr < l or r < ql) return; if (ql <= l and r <= qr) { st[v].lz = 1; relax(l, r, v); return; } create(v); int mid = (l+r)>>1; update(ql, qr, l, mid, st[v].li); update(ql, qr, mid+1, r, st[v].ri); st[v].res = st[st[v].li].res + st[st[v].ri].res; } int getans(int ql, int qr, int l, int r, int v) { relax(l, r, v); if (qr < l or r < ql) return 0; if (ql <= l and r <= qr) return st[v].res; create(v); int mid = (l+r)>>1; return getans(ql, qr, l, mid, st[v].li) + getans(ql, qr, mid + 1, r, st[v].ri); } }; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; SegTree st; st.init(100005); int c = 0, n = 100000001; while (q--) { int t, x, y; cin >> t >> x >> y; x += c; y += c; if (t == 1) { c = st.getans(x, y, 1, n, 1); cout << c << '\n'; } else { st.update(x, y, 1, n, 1); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...