#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
node* lft;
node* rght;
ll l;
ll p;
ll sm;
};
node* head=new node;
ll sum(node* now, ll a, ll b){
if (now->p < a || b < now->l){
return 0;
}
if (a <= now->l && now->p <= b){
return now->sm;
}
if (now->p - now->l + 1 == now->sm){
if (!(now->lft)){
now->lft=new node;
now->lft->l=now->l;
now->lft->p=(now->l+now->p)/2;
now->lft->sm=now->sm/2;
now->lft->lft=nullptr;
now->lft->rght=nullptr;
}
if (!(now->rght)){
now->rght=new node;
now->rght->l=(now->l+now->p)/2+1;
now->rght->p=now->p;
now->rght->sm=now->sm/2;
now->rght->lft=nullptr;
now->rght->rght=nullptr;
}
}
return (now->lft?sum(now->lft,a,b):0)+(now->rght?sum(now->rght,a,b):0);
}
void add(node* now, ll a, ll b){
if (now->p < a || b < now->l)return;
if (a <= now->l && now->p <= b){
now->sm=(now->p - now->l + 1);
return;
}
if (!(now->lft)){
now->lft=new node;
now->lft->l=now->l;
now->lft->p=(now->l+now->p)/2;
now->lft->sm=now->sm/2;
now->lft->lft=nullptr;
now->lft->rght=nullptr;
}
if (!(now->rght)){
now->rght=new node;
now->rght->l=(now->l+now->p)/2+1;
now->rght->p=now->p;
now->rght->sm=now->sm/2;
now->rght->lft=nullptr;
now->rght->rght=nullptr;
}
add(now->lft,a,b);
add(now->rght,a,b);
now->sm=now->lft->sm + now->rght->sm;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll m;
cin >> m;
head->l=0;
head->p=INT_MAX>>1;
head->sm=0;
head->lft=nullptr;
head->rght=nullptr;
ll d,a,b,c=0;
for (ll i = 1; i<=m; i++){
cin >> d >> a >> b;
if (d==1){
c=sum(head,a+c,b+c);
cout << c << '\n';
}
else{
add(head,a+c,b+c);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
