#include<iostream>
using namespace std;
typedef long long ll;
int n,q;
ll l[300001],r[300001];
int t[300001],p[300001];
ll s[300001],e[300001];
int a[300001],c[300001];
ll b[300001],d[300001];
ll ans[300001];
struct info{
ll l,r;
ll cost,to;//
};
info zero={(ll)-1e18,(ll)1e18,-1,0};
info f(info l,info r){
if(l.cost!=-1){
l.cost+=max(l.to-r.r,0LL);
l.to=min(r.r,max(l.to,r.l));
if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
}
else if(l.l>r.r){
l={l.l,l.l,l.l-r.r,r.r};
if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
}
else if(l.r<r.l){
l={l.r,l.r,0,r.l};
if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
}
else{
l={max(l.l,r.l),min(l.r,r.r),-1,168};
}
return l;
}
info g[1<<20];
void upd(int id,int l,int r,int up,ll us,ll ue){
if(l==r){
g[id]={us,ue,-1,168};
return;
}
int mid=(l+r)/2;
if(up<=mid) upd(id*2,l,mid,up,us,ue);
else upd(id*2+1,mid+1,r,up,us,ue);
g[id]=f(g[id*2],g[id*2+1]);
}
info qry(int id,int l,int r,int ql,int qr){
if(l>qr || r<ql) return zero;
if(ql<=l && r<=qr) return g[id];
int mid=(l+r)/2;
return f(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> q;
for(int i=1; i<n ;i++) cin >> l[i] >> r[i];
for(int i=1; i<n ;i++) upd(1,1,n,i,l[i]-i,r[i]-i-1);
for(int i=1; i<=q ;i++){
cin >> t[i];
if(t[i]==1){
cin >> p[i] >> s[i] >> e[i];
upd(1,1,n,p[i],s[i]-p[i],e[i]-p[i]-1);
}
else{
cin >> a[i] >> b[i] >> c[i] >> d[i];
if(a[i]>c[i]) continue;
if(a[i]==c[i]){
ans[i]=max(b[i]-d[i],0LL);
continue;
}
b[i]-=a[i],d[i]-=c[i];
info x={b[i],b[i],0,b[i]};
info y={d[i],d[i],0,d[i]};
info w=qry(1,1,n,a[i],c[i]-1);
info z=f(x,f(qry(1,1,n,a[i],c[i]-1),y));
ans[i]=z.cost;
}
}
for(int i=1; i<n ;i++) upd(1,1,n,n-i,l[i]+i+1,r[i]+i);
for(int i=1; i<=q ;i++){
if(t[i]==1) upd(1,1,n,n-p[i],s[i]+p[i]+1,e[i]+p[i]);
else{
if(a[i]<=c[i]) continue;
b[i]+=a[i],d[i]+=c[i];
info x={b[i],b[i],0,b[i]};
info y={d[i],d[i],0,d[i]};
info z=f(x,f(qry(1,1,n,n-a[i]+1,n-c[i]),y));
ans[i]=z.cost;
}
}
for(int i=1; i<=q ;i++) if(t[i]==2) cout << ans[i] << '\n';
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:73:9: warning: variable 'w' set but not used [-Wunused-but-set-variable]
info w=qry(1,1,n,a[i],c[i]-1);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1090 ms |
67276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
