//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
int s1,s2,e1,e2,sz;
ll c1,c2;
};
const int mxn=3e5+5;
vector<vector<node>> segtree(2,vector<node>(mxn*4));
int n,q;
int L[mxn],R[mxn];
node trash;
int cnt=0;
void merge(node &ans,node &a,node &b){
cnt++;
assert(cnt<10000);
if(a.sz==-1){
ans=b;
return;
}
if(b.sz==-1){
ans=a;
return;
}
ans.sz=a.sz+b.sz;
ans.s1=a.s1;
ans.s2=a.s2;
{
ans.c1=a.c1;
if(a.e1>b.s1){
ans.c1+=b.c1+(a.e1-b.s1);
ans.e1=b.e1;
}
else if(a.e1>=b.s2){
ll dif=b.c1-b.c2;
ans.c1+=b.c2+max(0ll,dif-(b.s1-a.e1));
int res=a.e1+b.sz;
if(res>b.e1){
ans.e1=b.e1;
}
else{
ans.e1=max(res,b.e2);
}
}
else{
ans.c1+=b.c2;
ans.e1=b.e2;
}
}
{
ans.c2=a.c2;
if(a.e2>b.s1){
ans.c2+=b.c1+(a.e2-b.s1);
ans.e2=b.e1;
}
else if(a.e2>=b.s2){
ll dif=b.c1-b.c2;
ans.c2+=b.c2+max(0ll,dif-(b.s1-a.e2));
int res=a.e2+b.sz;
if(res>b.e1){
ans.e2=b.e1;
}
else{
ans.e2=max(res,b.e2);
}
}
else{
ans.c2+=b.c2;
ans.e2=b.e2;
}
}
}
void build(int id,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=R[l]-1;
segtree[id][v].s2=L[l];
segtree[id][v].e1=R[l];
segtree[id][v].e2=L[l]+1;
segtree[id][v].c1=segtree[id][v].c2=0;
segtree[id][v].sz=1;
return;
}
int mid=(l+r)/2;
build(id,l,mid,v*2);
build(id,mid+1,r,v*2+1);
merge(segtree[id][v],segtree[id][v*2],segtree[id][v*2+1]);
}
void update(int id,int pos,int s,int e,int l=1,int r=n-1,int v=1){
if(l==r){
segtree[id][v].s1=e-1;
segtree[id][v].s2=s;
segtree[id][v].e1=e;
segtree[id][v].e2=s+1;
return;
}
int mid=(l+r)/2;
if(pos<=mid) update(id,pos,s,e,l,mid,v*2);
else update(id,pos,s,e,mid+1,r,v*2+1);
merge(segtree[id][v],segtree[id][v*2],segtree[id][v*2+1]);
}
node query(int id,int tl,int tr,int l=1,int r=n-1,int v=1){
if(r<tl or tr<l){
return trash;
}
if(tl<=l and r<=tr){
return segtree[id][v];
}
int mid=(l+r)/2;
node ans;
node a=query(id,tl,min(mid,tr),l,mid,v*2);
node b=query(id,max(mid+1,tl),tr,mid+1,r,v*2+1);
merge(ans,a,b);
return ans;
}
signed main() {_
trash.sz=-1;
cin>>n>>q;
for(int i=1;i<n;i++){
cin>>L[i]>>R[i];
}
build(0);
reverse(L+1,L+n);
reverse(R+1,R+n);
build(1);
reverse(L+1,L+n);
reverse(R+1,R+n);
for(int i=0;i<q;i++){
int t;
cin>>t;
if(t==1){
ll p,s,e;
cin>>p>>s>>e;
update(0,p,s,e);
update(1,n-p,s,e);
}
else{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a==c){
cout<<max(0,b-d)<<'\n';
continue;
}
node tmp;
if(a<c){
tmp=query(0,a,c-1);
}
else{
a=n-a+1;
c=n-c+1;
//swap(b,d);
tmp=query(1,a,c-1);
}
/*cout<<tmp.sz<<'\n';
cout<<tmp.s1<<' '<<tmp.s2<<'\n';
cout<<tmp.e1<<' '<<tmp.e2<<'\n';
cout<<tmp.c1<<' '<<tmp.c2<<'\n';*/
ll ans=0;
int fin;
if(b>tmp.s1){
ans+=tmp.c1+(b-tmp.s1);
fin=tmp.e1;
}
else if(b>=tmp.s2){
ll dif=tmp.c1-tmp.c2;
ans+=tmp.c2+max(0ll,dif-(tmp.s1-b));
int res=b+tmp.sz;
if(res>tmp.e1){
fin=tmp.e1;
}
else{
fin=max(res,tmp.e2);
}
}
else{
ans+=tmp.c2;
fin=tmp.e2;
}
cout<<ans+max(0,fin-d)<<'\n';;
}
}
return 0;
}
//maybe its multiset not set
Compilation message
timeleap.cpp: In function 'void setIO(std::string)':
timeleap.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
141148 KB |
Output is correct |
| 2 |
Correct |
24 ms |
141148 KB |
Output is correct |
| 3 |
Correct |
23 ms |
141320 KB |
Output is correct |
| 4 |
Correct |
23 ms |
141108 KB |
Output is correct |
| 5 |
Correct |
23 ms |
141140 KB |
Output is correct |
| 6 |
Correct |
22 ms |
141148 KB |
Output is correct |
| 7 |
Correct |
24 ms |
141136 KB |
Output is correct |
| 8 |
Correct |
23 ms |
141148 KB |
Output is correct |
| 9 |
Correct |
25 ms |
141080 KB |
Output is correct |
| 10 |
Correct |
24 ms |
141232 KB |
Output is correct |
| 11 |
Runtime error |
97 ms |
195124 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
195636 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
141148 KB |
Output is correct |
| 2 |
Correct |
24 ms |
141148 KB |
Output is correct |
| 3 |
Correct |
23 ms |
141320 KB |
Output is correct |
| 4 |
Correct |
23 ms |
141108 KB |
Output is correct |
| 5 |
Correct |
23 ms |
141140 KB |
Output is correct |
| 6 |
Correct |
22 ms |
141148 KB |
Output is correct |
| 7 |
Correct |
24 ms |
141136 KB |
Output is correct |
| 8 |
Correct |
23 ms |
141148 KB |
Output is correct |
| 9 |
Correct |
25 ms |
141080 KB |
Output is correct |
| 10 |
Correct |
24 ms |
141232 KB |
Output is correct |
| 11 |
Runtime error |
97 ms |
195124 KB |
Execution killed with signal 6 |
| 12 |
Halted |
0 ms |
0 KB |
- |
