Submission #1300333

#TimeUsernameProblemLanguageResultExecution timeMemory
1300333ThunnusMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
323 ms263692 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define pii pair<int, int> #define fi first #define se second #define sz(x) (int)(x).size() const int MAXN = 1e9 + 1; struct SegTree{ struct Node{ int sum, lazy, lc, rc; Node(int sum, int lazy, int lc, int rc) : sum(sum), lazy(lazy), lc(lc), rc(rc) {} Node() : Node(0, 0, -1, -1) {} }; int idx = 2; vector<Node> st; SegTree() : st(2, Node()) {} inline int extend(){ while(idx >= sz(st)){ st.emplace_back(Node()); } return idx++; } inline void extend(int &c){ if(c == -1){ c = extend(); } return; } inline void combine(int v){ int res = 0; if(st[v].lc != -1){ res += st[st[v].lc].sum; } if(st[v].rc != -1){ res += st[st[v].rc].sum; } st[v].sum = res; return; } inline void apply(int v, int val, int len){ st[v].sum = len * val; st[v].lazy = val; return; } inline void propagate(int v, int tl, int mid, int tr){ if(st[v].lazy){ if(st[v].lc == -1){ st[v].lc = extend(); } if(st[v].rc == -1){ st[v].rc = extend(); } apply(st[v].lc, st[v].lazy, mid - tl + 1); apply(st[v].rc, st[v].lazy, tr - (mid + 1) + 1); st[v].lazy = 0; } return; } inline void update(int ul, int ur, int val, int v, int tl, int tr){ if(ul > tr || tl > ur) return; if(ul <= tl && tr <= ur){ apply(v, val, tr - tl + 1); return; } int mid = (tl + tr) >> 1; propagate(v, tl, mid, tr); if(ul <= mid){ if(st[v].lc == -1){ st[v].lc = extend(); } update(ul, ur, val, st[v].lc, tl, mid); } if(mid + 1 <= ur){ if(st[v].rc == -1){ st[v].rc = extend(); } update(ul, ur, val, st[v].rc, mid + 1, tr); } combine(v); return; } inline int query(int ql, int qr, int v, int tl, int tr){ if(ql > tr || tl > qr) return 0ll; if(ql <= tl && tr <= qr) return st[v].sum; int mid = (tl + tr) >> 1; propagate(v, tl, mid, tr); if(ql <= mid && mid + 1 <= qr){ if(st[v].lc == -1){ st[v].lc = extend(); } if(st[v].rc == -1){ st[v].rc = extend(); } return query(ql, qr, st[v].lc, tl, mid) + query(ql, qr, st[v].rc, mid + 1, tr); } else if(ql <= mid){ if(st[v].lc == -1){ st[v].lc = extend(); } return query(ql, qr, st[v].lc, tl, mid); } else{ if(st[v].rc == -1){ st[v].rc = extend(); } return query(ql, qr, st[v].rc, mid + 1, tr); } } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int m, c = 0; cin >> m; SegTree st; while(m--){ int d, l, r; cin >> d >> l >> r; if(d == 1){ l += c, r += c; c = st.query(l, r, 1, 1, MAXN); cout << c << "\n"; } else{ l += c, r += c; st.update(l, r, 1, 1, 1, MAXN); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...