제출 #1253633

#제출 시각아이디문제언어결과실행 시간메모리
1253633BalsaMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
422 ms254748 KiB
#include <bits/stdc++.h> using namespace std; using ll = int; const bool NO_OPERATION = 0; struct segtree { struct node { ll sum = 0; bool opr = NO_OPERATION; node *left = nullptr, *right = nullptr; void extend(ll lx, ll rx) { if (left == nullptr && rx-lx > 1) { left = new node(); right = new node(); } } void prop(ll lx, ll rx) { if (rx-lx == 1) return; if (opr == NO_OPERATION) return; left->opr = right->opr = opr; left->sum = right->sum = (rx-lx)/2 * opr; opr = NO_OPERATION; } void set(ll l, ll r, ll v, ll lx, ll rx) { extend(lx, rx); prop(lx, rx); if (rx <= l || lx >= r) return; if (lx >= l && rx <= r) { opr = 1; sum = (rx-lx); return; } ll m = (lx+rx)/2; left->set(l, r, v, lx, m); right->set(l, r, v, m, rx); sum = left->sum + right->sum; } ll query(ll l, ll r, ll lx, ll rx) { extend(lx, rx); prop(lx, rx); if (rx <= l || lx >= r) return 0; if (lx >= l && rx <= r) return sum; ll m = (lx+rx)/2; return left->query(l, r, lx, m) + right->query(l, r, m, rx); } }; ll size = 1; node* root = new node(); segtree(ll n) { while (size < n) size*=2; } void set(ll l, ll r, ll v) { root->set(l, r, v, 0, size); } ll query(ll l, ll r) { return root->query(l, r, 0, size); } }; void solve() { segtree st(1e9); ll c = 0; ll m; cin >> m; for (ll q = 0; q < m; q++) { ll t, l, r; cin >> t >> l >> r; l--; if (t == 2) { st.set(l + c, r + c, 1); } else { c = st.query(l + c, r + c); cout << c << '\n'; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...