| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1051512 | isaachew | Bitaro, who Leaps through Time (JOI19_timeleap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
/*
"Tree segtree" (HLD)
Backwards?
Intervals overlap -> fine
Intervals do not overlap -> single point
*/
struct node{
long long delay,min,max,start,back;//max(min(x+delay,max),min) (max is when num. leaps start increasing)
node(long long a=0,long long b=-1e18,long long c=1e18,long long d=1e18,long long e=0){
delay=a,min=b,max=c,start=d,back=e;
}
node combine(node oth){
node undel=node(delay+oth.delay,min+oth.delay,max+oth.delay,start+oth.delay,back+oth.back);//put oth's delay at start
long long fmin=std::max(std::min(undel.min,oth.max),oth.min);//clamp to next one
long long fmax=std::max(std::min(undel.max,oth.max),oth.min);//clamp to next one
long long fstart=min==max?undel.start:std::min(std::max(oth.start,undel.min),undel.max);//clamp to this one if there is a range, otherwise just use this start
long long fback=std::min(1e18,back+oth.back+std::max(0ll,undel.min-oth.start));//cap for overflow
return node(delay+oth.delay,fmin,fmax,fstart,fback);
}
long long nleaps(long long st,long long et){
long long stdest=std::max(std::min(st+delay,max),min);
return std::max((st+delay)-start,0ll)+std::max(stdest-et,0ll)+back;
}
};
struct segtree{
int size;
std::vector<node> nodes,rnodes;//one forward, one reverse
segtree(int n){
size=n;
nodes.resize(2*n-1);
rnodes.resize(2*n-1);
}
void update(int p,node val,int nl,int nr,int ni){
if(p<nl||p>=nr)return;
if(nl+1>=nr){
nodes[ni]=val;
rnodes[ni]=val;
return;
}
int nm=(nl+nr)/2;
update(p,val,nl,nm,ni+1);
update(p,val,nm,nr,ni+2*(nm-nl));
nodes[ni]=nodes[ni+1].combine(nodes[ni+2*(nm-nl)]);
rnodes[ni]=rnodes[ni+2*(nm-nl)].combine(rnodes[ni+1]);
}
void update(int p,node val){update(p,val,0,size,0);}
node query(int l,int r,int nl,int nr,int ni){
if(l>=nr||r<=nl)return node();
if(l<=nl&&r>=nr)return nodes[ni];
int nm=(nl+nr)/2;
node res1=query(l,r,nl,nm,ni+1);
node res2=query(l,r,nm,nr,ni+2*(nm-nl));
return res1.combine(res2);
}
node query(int l,int r){return query(l,r,0,size,0);}
node rquery(int l,int r,int nl,int nr,int ni){
if(l>=nr||r<=nl)return node();
if(l<=nl&&r>=nr)return rnodes[ni];
int nm=(nl+nr)/2;
node res1=rquery(l,r,nl,nm,ni+1);
node res2=rquery(l,r,nm,nr,ni+2*(nm-nl));
return res2.combine(res1);
}
node rquery(int l,int r){return rquery(l,r,0,size,0);}
};
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n,q;
std::cin>>n>>q;
segtree seg(n);
for(int i=0;i<n-1;i++){
int a,b;
std::cin>>a>>b;
seg.update(i,node(1,a+1,b,b));
}
for(int i=0;i<q;i++){
int x;
std::cin>>x;
if(x==1){
int p,s,e;
std::cin>>p>>s>>e;
p--;
seg.update(p,node(1,s+1,e,e));
}else{
int a,b,c,d;
std::cin>>a>>b>>c>>d;
a--,c--;
if(a<c){
std::cout<<seg.query(a,c).nleaps(b,d)<<'\n';
}else{
std::cout<<seg.rquery(c,a).nleaps(b,d)<<'\n';
}
}
}
}