#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const ll en = 1e9;
const ll mx = 6e6+5;
ll lzy[mx],seg[mx],c1[mx],c2[mx],cnt=1;
void make_c(int l,int r,int u){
if(l==r) return;
c1[u]=++cnt,c2[u]=++cnt;
}
void push(int l,int r,int u){
if(l==r)
seg[u]=max(seg[u],lzy[u]);
else
if(lzy[u]==1){
seg[u]=r-l+1;
lzy[c1[u]]=1,
lzy[c2[u]]=1;
}
lzy[u]=0;
}
void upd(ll L,ll R,ll u=1,ll l=1,ll r=en){
if(c1[u]==0||c2[u]==0)
make_c(l,r,u);
push(l,r,u);
if(L<=l&&r<=R)
lzy[u]=1,
push(l,r,u);
else if(!(R<l||r<L)){
push(l,r,u);
int m=(l+r)/2;
upd(L,R,c1[u],l,m);
upd(L,R,c2[u],m+1,r);
seg[u]=seg[c1[u]]+seg[c2[u]];
}
}
ll red(ll L,ll R,ll u=1,ll l=1,ll r=en){
if(c1[u]==0||c2[u]==0)
make_c(l,r,u);
push(l,r,u);
if (L<=l&&r<=R)
return seg[u];
else if(R<l||r<L)
return 0;
else{
int m=(l+r)/2;
return red(L,R,c1[u],l,m)
+red(L,R,c2[u],m+1,r);
}
}
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll c=0,m;cin>>m;
for(ll d,l,r;m--;){
cin>>d>>l>>r;
l+=c,r+=c;
if(d==1){
ll t=red(l,r);
cout<<t<<endl;
c+=t;
}
if(d==2)
upd(l,r);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
