#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 time | Memory | Grader output |
---|
Fetching results... |