Submission #1240726

#TimeUsernameProblemLanguageResultExecution timeMemory
1240726cosminccc7Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; int q,ct; struct tree { int st, dr, sum = 0; tree *f1 = NULL, *f2 = NULL; tree(int a, int b) { st = a; dr = b; } }; void transmite(tree *&nod) { int mij = (nod->st + nod->dr) / 2; if (!nod->f1) { nod->f1 = new tree(nod->st, mij); nod->f2 = new tree(mij + 1, nod->dr); } } void update(tree *&nod, int a, int b) { if (b < nod->st || a > nod->dr) return; // fără intersecție if (nod->sum == nod->dr - nod->st + 1) return; // deja complet acoperit if (a <= nod->st && nod->dr <= b) { nod->sum = nod->dr - nod->st + 1; return; } transmite(nod); update(nod->f1, a, b); update(nod->f2, a, b); nod->sum = nod->f1->sum + nod->f2->sum; } int query(tree *&nod, int a, int b) { if (b < nod->st || a > nod->dr) return 0; // fără intersecție if (a <= nod->st && nod->dr <= b ) return nod->sum; if(nod->sum==0)return 0; if(nod->sum == nod->dr - nod->st + 1) return min(b,nod->dr)-max(a,nod->st)+1; return query(nod->f1, a, b) + query(nod->f2, a, b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); tree *a = new tree(1, 1000000000); cin >> q; for (int i = 1; i <= q; i++) { int tip, st, dr; cin >> tip >> st >> dr; st+=ct,dr+=ct; if (tip == 2) update(a, st, dr); else {int val= query(a, st, dr); cout << val<< '\n'; ct+=val;} } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...