#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
struct node
{
int sum,lazy;
int tole,tori;
};
vector<node> aint;
void propagate(int nod, int st, int dr)
{
if(aint[nod].lazy==0)
return;
int le = aint[nod].tole;
int ri = aint[nod].tori;
int mij=(st+dr)/2;
aint[le].sum = mij-st+1;
aint[le].lazy = 1;
aint[ri].sum = dr-mij;
aint[ri].lazy = 1;
aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return;
if(st==dr)
{
aint[nod].sum = ri-le+1;
return;
}
if(aint[nod].tole==-1)
{
aint[nod].tole=aint.size();
aint.push_back({0,0,-1,-1});
}
if(aint[nod].tori==-1)
{
aint[nod].tori=aint.size();
aint.push_back({0,0,-1,-1});
}
propagate(nod,st,dr);
int mij=(st+dr)/2;
upd(aint[nod].tole,st,mij,le,min(mij,ri));
upd(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
aint[nod].sum = aint[aint[nod].tole].sum + aint[aint[nod].tori].sum;
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return 0;
if(le==st && dr==ri)
return aint[nod].sum;
if(aint[nod].tole==-1)
{
aint[nod].tole=aint.size();
aint.push_back({0,0,-1,-1});
}
if(aint[nod].tori==-1)
{
aint[nod].tori=aint.size();
aint.push_back({0,0,-1,-1});
}
propagate(nod,st,dr);
int mij=(st+dr)/2;
return qry(aint[nod].tole,st,mij,le,min(mij,ri)) +
qry(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
aint.reserve(40000000);
int m,c=0,d,x,y;
cin>>m;
aint.push_back({0,0,-1,-1});
while(m--)
{
cin>>d>>x>>y;
x+=c;
y+=c;
if(d==1)
{
c = qry(0,1,INF,x,y);
cout<<c<<"\n";
}
else
{
upd(0,1,INF,x,y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
2086 ms |
30184 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
