Submission #1051515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051515		isaachew	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	482 ms	67664 KiB

timeleap

#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((long long)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';
            }
        }
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66