#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
#define endl '\n'
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
struct nd{int l,r;ll c;};
const int maxn=1<<19,inf=1ll<<60;
int n,q;
nd dat[2][maxn<<1];
nd merge(nd a,nd b,int t){
if(t)swap(a,b);
if(a.c<0){
if(b.c<0){
if(a.r<b.l)return nd{a.r,b.l,0};
else if(b.r<a.l)return nd{a.l,b.r,a.l-b.r};
else return nd{max(a.l,b.l),min(a.r,b.r),-1};
}else{
int s=max(a.l,min(a.r,b.l));
return nd{s,b.r,b.c+max(0,s-b.l)};
}
}else{
if(b.c<0){
int t=max(b.l,min(b.r,a.r));
return nd{a.l,t,a.c+max(0,a.r-t)};
}else{
return nd{a.l,b.r,a.c+b.c+max(0,a.r-b.l)};
}
}
}
void mnt(int idx){
dat[0][idx]=merge(dat[0][lch],dat[0][rch],0);
dat[1][idx]=merge(dat[1][lch],dat[1][rch],1);
}
void ch(int l,int r,int idx,int p,int s,int e){
if(l+1==r){
dat[0][idx]=nd{s-l,e-l-1,-1};
dat[1][idx]=nd{s+l+1,e+l,-1};
}else{
if(p<mid)ch(l,mid,lch,p,s,e);
else ch(mid,r,rch,p,s,e);
mnt(idx);
}
}
nd qr(int l,int r,int idx,int a,int b,int t){
if(b<=l||r<=a)return nd{-inf,inf,-1};
else if(a<=l&&r<=b)return dat[t][idx];
else return merge(qr(l,mid,lch,a,b,t),qr(mid,r,rch,a,b,t),t);
}
main(){
IOS;
cin>>n>>q;
REP(i,1,n){
int l,r;cin>>l>>r;
ch(1,n,0,i,l,r);
}
REP(_,0,q){
int t,p,s,e,a,b,c,d;cin>>t;
if(t==1){
cin>>p>>s>>e;
ch(1,n,0,p,s,e);
}else{
cin>>a>>b>>c>>d;
int t=a>c;
if(t)cout<<merge(nd{d+c,d+c,0},merge(qr(1,n,0,c,a,t),nd{b+a,b+a,0},t),t).c<<endl;
else cout<<merge(nd{b-a,b-a,0},merge(qr(1,n,0,a,c,t),nd{d-c,d-c,0},t),t).c<<endl;
}
}
}
Compilation message
timeleap.cpp:13:29: warning: overflow in implicit constant conversion [-Woverflow]
const int maxn=1<<19,inf=1ll<<60;
~~~^~~~
timeleap.cpp: In function 'void ch(int, int, int, int, int, int)':
timeleap.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
timeleap.cpp:48:8: note: in expansion of macro 'mid'
if(p<mid)ch(l,mid,lch,p,s,e);
^~~
timeleap.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
timeleap.cpp:48:17: note: in expansion of macro 'mid'
if(p<mid)ch(l,mid,lch,p,s,e);
^~~
timeleap.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
timeleap.cpp:49:11: note: in expansion of macro 'mid'
else ch(mid,r,rch,p,s,e);
^~~
timeleap.cpp: In function 'nd qr(int, int, int, int, int, int)':
timeleap.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
timeleap.cpp:57:25: note: in expansion of macro 'mid'
else return merge(qr(l,mid,lch,a,b,t),qr(mid,r,rch,a,b,t),t);
^~~
timeleap.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
timeleap.cpp:57:43: note: in expansion of macro 'mid'
else return merge(qr(l,mid,lch,a,b,t),qr(mid,r,rch,a,b,t),t);
^~~
timeleap.cpp: At global scope:
timeleap.cpp:60:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
741 ms |
39200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
