Submission #888541

#TimeUsernameProblemLanguageResultExecution timeMemory
888541dwuyMonkey and Apple-trees (IZhO12_apple)C++14
100 / 100
224 ms56800 KiB
#include <bits/stdc++.h> using namespace std; struct Node{ bool lz; int sum; Node *l, *r; Node(){ this->lz = 0; this->sum = 0; this->l = this->r = NULL; } }; struct SMT{ int n; Node *root; SMT(int n=0){ this->n = n; this->root = new Node(); } void update(Node *cur, int l, int r, const int &u, const int &v){ if(l>v || r<u) return; if(l>=u && r<=v){ cur->lz = 1; cur->sum = (r-l+1); return; } int mid = (l+r)>>1; if(!cur->l && u<=mid) cur->l = new Node(); if(!cur->r && mid<v) cur->r = new Node(); update(cur->l, l, mid, u, v); update(cur->r, mid+1, r, u, v); cur->sum = (cur->l? cur->l->sum : 0) + (cur->r? cur->r->sum : 0); if(cur->lz) cur->sum = r - l + 1; } void update(int l, int r){ update(root, 1, n, l, r); } int get(Node *cur, int l, int r, const int &u, const int &v){ if(l>v || r<u || !cur || !cur->sum) return 0; if(l>=u && r<=v) return cur->sum; int mid = (l+r)>>1; int L = get(cur->l, l, mid, u, v); int R = get(cur->r, mid+1, r, u, v); return cur->lz? min(r, v) - max(l, u) + 1 : L + R; } int get(int l, int r){ return get(root, 1, n, l, r); } }; void solve(){ int q; cin >> q; SMT smt(1000000000); int C = 0; while(q--){ int oper, l, r; cin >> oper >> l >> r; l += C; r += C; if(oper == 2) smt.update(l, r); else{ C = smt.get(l, r); cout << C << endl; } } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...