#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct tree
{
struct node
{
node *l,*r;
bool minval;
int cnt;
bool lazy;
node(int _cnt)
{
l=nullptr;
r=nullptr;
minval=0;cnt=_cnt;
}
};
node* root=nullptr;
node* xd;
node* merge(node *n1,node *n2,int L,int R)
{
node *ret=new node(R-L+1);
int mid=(L+R)/2;
if(!n1)
{
tie(ret->minval,ret->cnt)=make_pair(n2->minval,n2->cnt);
if(ret->minval==0)ret->cnt+=mid-L+1;
else
{
ret->minval=0;
ret->cnt=mid-L+1;
}
ret->r=n2;
return ret;
}
if(!n2)
{
tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt);
if(ret->minval==0)ret->cnt+=R-mid;
else
{
ret->minval=0;
ret->cnt=R-mid;
}
ret->l=n1;
return ret;
}
if(n1->minval==n2->minval)
{
tie(ret->minval,ret->cnt)=make_pair(n1->minval,n1->cnt+n2->cnt);
}
else tie(ret->minval,ret->cnt)=min(make_pair(n1->minval,n1->cnt),make_pair(n2->minval,n2->cnt));
ret->l=n1;ret->r=n2;
return ret;
}
node* push(node* &t,int L,int R)
{
//cout<<L<<" "<<R<<" pushed\n";
if(!t)t=new node(R-L+1);
if(t->lazy)
{
if(L!=R)
{
int mid=(L+R)/2;
if(t->l)
{
t->l->lazy=1;
}
else
{
t->l=new node(mid-L+1);
t->l->lazy=1;
}
if(t->r)
{
t->r->lazy=1;
}
else
{
t->r=new node(R-mid);
t->r->lazy=1;
}
}
t->minval=1;
t->lazy=0;
}
return t;
}
node* upd(node *t,int L,int R,int ql,int qr)
{
//cout<<L<<" "<<R<<"\n";
//op++;
//if(op>100)return;
//cout<<"?\n";
//bool pr=0;
//if(t&&t->lazy)pr=1;
t=push(t,L,R);
/*if(pr)
{
cout<<"shre\n";
if(t->l)cout<<t->l->minval<<" "<<t->l->lazy<<endl;
if(t->r)cout<<t->r->minval<<" "<<t->r->lazy<<endl;
}*/
//cout<<"?\n";
if(L>qr||R<ql)return NULL;
if(L>=ql&&R<=qr)
{
t->lazy=1;
t=push(t,L,R);
//if(t)cout<<L<<" "<<R<<endl;
return t;
}
int mid=(L+R)/2;
if(mid+1>qr)
{
//cout<<"1:\n";
//if(!t->l)cout<<"wtf\n";
//else cout<<t->l->minval<<" "<<t->l->cnt<<endl;
//if(!t->l)t->l=new node(mid-L+1);
//cout<<"$#@$#@\n";
t->l=upd(t->l,L,mid,ql,qr);
//cout<<":1\n";
}
else if(mid<ql)
{
//cout<<"2:\n";
t->r=upd(t->r,mid+1,R,ql,qr);
//cout<<":2\n";
}
else
{
//cout<<"3:\n";
t->l=upd(t->l,L,mid,ql,qr);
t->r=upd(t->r,mid+1,R,ql,qr);
//cout<<":3\n";
}
if(t->l&&t->l->lazy)t->l=push(t->l,L,mid);
if(t->r&&t->r->lazy)t->r=push(t->r,mid+1,R);
//cout<<L<<" "<<R<<endl;
//cout<<"t->l:";
//if(t->l)cout<<t->l->minval<<" "<<t->l->cnt<<" "<<t->l->lazy<<endl;
//else cout<<endl;
//cout<<"t->r:";
//if(t->r)cout<<t->r->minval<<" "<<t->r->cnt<<" "<<t->r->lazy<<endl;
//else cout<<endl;
t=merge(t->l,t->r,L,R);
//cout<<"merged to:\n";
//cout<<t->minval<<" "<<t->cnt<<" "<<t->lazy<<endl;
return t;
//if(t)cout<<L<<" "<<R<<endl;
}
int query(node *t,int L,int R,int ql,int qr)
{
//cout<<L<<" "<<R<<endl;
t=push(t,L,R);
if(L>qr||R<ql)return 0;
if(L>=ql&&R<=qr)
{
if(t->minval==0)return t->cnt;
else return 0;
//return t;
}
int mid=(L+R)/2;
if(mid<ql)return query(t->r,mid+1,R,ql,qr);
else if(mid+1>qr)return query(t->l,L,mid,ql,qr);
return query(t->l,L,mid,ql,qr)+query(t->r,mid+1,R,ql,qr);
}
void print(node* t,int L,int R)
{
if(!t)return;
//if(t->l&&t->r)t=push(t,L,R);
//cout<<L<<" "<<R<<" "<<t->minval<<" "<<t->cnt<<" "<<t->lazy<<endl;
print(t->l,L,(L+R)/2);
print(t->r,(L+R)/2+1,R);
}
}st;
int main()
{
/*ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);*/
int c=0;
int m,d,x,y,xd;
cin>>m;
/*if(m>60000)
{
cout<<0<<endl;
return 0;
}*/
while(m--)
{
cin>>d>>x>>y;
x+=c;y+=c;
//cout<<"#@$%$#@$\n";
if(d==1)
{
xd=st.query(st.root,1,INF,x,y);
c=y-x+1-xd;
cout<<c<<endl;
}
else
{
//cout<<"5%\n";
st.root=st.upd(st.root,1,INF,x,y);
}
//st.print(st.root,1,INF);
//cout<<"fdsf "<<cnt_nodes<<endl;
//int xd=st.query(st.root,1,INF,1,INF);
//cout<<xd<<" "<<INF-xd<<endl;
//cnt_nodes=0;
}
/*for(int i=0;i<10;i++)
{
for(int j=i+1;j<10000;j++)
{
st.root=st.upd(st.root,0,INF,i,j);
}
}
st.print(st.root);
cout<<cnt_nodes<<endl;*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
47 ms |
16236 KB |
Output is correct |
| 5 |
Correct |
60 ms |
20076 KB |
Output is correct |
| 6 |
Correct |
60 ms |
20076 KB |
Output is correct |
| 7 |
Correct |
60 ms |
20204 KB |
Output is correct |
| 8 |
Correct |
443 ms |
125292 KB |
Output is correct |
| 9 |
Correct |
845 ms |
232684 KB |
Output is correct |
| 10 |
Correct |
901 ms |
248096 KB |
Output is correct |
| 11 |
Correct |
877 ms |
259772 KB |
Output is correct |
| 12 |
Runtime error |
901 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
