#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 20000000
#define N 300005
#define MOD 998244353
#define KOK 700
using namespace std;
struct range {
int lb,rb;
int ps;
ll cost;
int near;
};
struct seg {
range pre,suf;
} S[N*4];
int n,q;
int l[N],r[N];
range combine(range l,range r) {
range res;
tie(res.lb,res.rb)=tie(l.lb,l.rb); // lb,rb
int ct=l.ps;
//cerr<<"ct : "<<ct<<"\n";
res.cost=l.cost+r.cost; // cost ~~~~
if(ct<=r.lb) {
res.lb=r.lb-1;
umax(res.rb,r.lb-1);
l.near=res.rb-res.lb;
res.near=min(l.near,r.near); // near
res.ps=r.ps; // ps
}
else {
int df=ct-r.lb;
if(df>r.near) {
int dfn=df-r.near;
res.cost+=dfn; // cost +
if(r.near) res.ps=r.ps+r.near; // ps
else res.ps=r.ps;
r.near=0; // near
}
else {
res.ps=r.ps+df;
r.near-=df;
}
res.near=min(l.near,r.near);
}
return res;
}
seg merge(seg a,seg b) {
seg res;
res.pre=combine(a.pre,b.pre);
res.suf=combine(b.suf,a.suf);
return res;
}
seg get_naive(int id) {
seg res;
res.suf=res.pre={l[id],r[id],l[id]+1,0,r[id]-l[id]};
return res;
}
seg get(int node,int bas,int son,int l,int r) {
if(bas>=l && son<=r) return S[node];
if(orta>l && orta<r) return merge(get(node<<1,bas,orta,l,r),get(node<<1|1,orta,son,l,r));
if(orta>l) return get(node<<1,bas,orta,l,r);
return get(node<<1|1,orta,son,l,r);
}
void up(int node,int bas,int son,int l,int r) {
if(bas==l && son==r) {
S[node]=get_naive(bas);
return ;
}
if(bas>=r || son<=l) return ;
up(node<<1,bas,orta,l,r);
up(node<<1|1,orta,son,l,r);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
void build(int node,int bas,int son) {
if(bas+1==son) {
S[node]=get_naive(bas);
return ;
}
build(node<<1,bas,orta);
build(node<<1|1,orta,son);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
int main() {
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++) {
scanf("%d %d",l+i,r+i);
r[i]--;
}
build(1,1,n);
//cerr<<get(1,1,n,1,5).suf.ps<<"\n";
//return 0;
while(q--) {
int t;
scanf("%d",&t);
if(t==1) {
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
tie(l[a],r[a])={b,c};
r[a]--;
up(1,1,n,a,a+1);
}
else {
int a,b,c,d;
scanf("%d %d %d %d",&a,&b,&c,&d);
range f={b,b,b,0,inf};
range s={d,d,d,0,0};
range ans;
if(a!=c) {
seg res=get(1,1,n,min(a,c),max(a,c));
ans=(a<c?res.pre:res.suf);
//cerr<<ans.cost<<' '<<ans.ps<<"\n";
ans=combine(f,ans);
ans=combine(ans,s);
}
else {
ans=combine(f,s);
}
printf("%lld\n",ans.cost);
}
}
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
timeleap.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",l+i,r+i);
~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
timeleap.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:199:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&a,&b,&c,&d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
814 ms |
87928 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 |
- |
