Submission #119770

#	Time	Username	Problem	Language	Result	Execution time	Memory
119770		errorgorn	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	1480 ms	269684 KiB

timeleap

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
int n;
ii input[300005];
inline int read() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}
struct stats{
    int l_time,r_time;
    long long time_used;
    long long powers_used;
    stats(int a,int b,int c, int d){
        l_time=a;
        r_time=b;
        time_used=c;
        powers_used=d;
    }
    stats(stats *i, stats *j){
        unions(i,j);
    }
    stats(stats *i){
        l_time=i->l_time;
        r_time=i->r_time;
        time_used=i->time_used;
        powers_used=i->powers_used;
    }
    void unions(stats *l,stats *r){
        powers_used=l->powers_used+r->powers_used;
        time_used=l->time_used+r->time_used;
        int left=l->l_time+l->time_used,right=l->r_time+l->time_used;
        if (max(left,r->l_time)<=min(right,r->r_time)){
            l_time=max(left,r->l_time)-l->time_used;
            r_time=min(right,r->r_time)-l->time_used;
        }
        else if (right<r->l_time){
            time_used+=r->l_time-right;
            l_time=l->r_time;
            r_time=l_time;
        }
        else{
            powers_used+=left-r->r_time;
            time_used-=left-r->r_time;
            l_time=l->l_time;
            r_time=l_time;
        }
    }
};
struct node{
    int s,e,m;
    stats *val;
    node *l,*r;
    node (int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1;
        if (s==e){
            val=new stats(input[s].first,input[s].second-1,1,0);
        }
        else{
            l=new node(s,m);
            r=new node(m+1,e);
            val=new stats(l->val,r->val);
        }
    }
    stats* query(int i,int j){
        if (s==i && e==j) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return new stats(l->query(i,m),r->query(m+1,j));
    }
    void update(int i){
        if (s==e){
            val=new stats(input[s].first,input[s].second-1,1,0);
        }
        else{
            if (i<=m) l->update(i);
            else r->update(i);
            val->unions(l->val,r->val);
        }
    }
}*root;
struct rnode{
    int s,e,m;
    stats *val;
    rnode *l,*r;
    rnode (int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1;
        if (s==e){
            val=new stats(input[n-s].first,input[n-s].second-1,1,0);
        }
        else{
            l=new rnode(s,m);
            r=new rnode(m+1,e);
            val=new stats(l->val,r->val);
        }
    }
    stats* query(int i,int j){
        if (s==i && e==j) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return new stats(l->query(i,m),r->query(m+1,j));
    }
    void update(int i){
        if (s==e){
            val=new stats(input[n-s].first,input[n-s].second-1,1,0);
        }
        else{
            if (i<=m) l->update(i);
            else r->update(i);
            val->unions(l->val,r->val);
        }
    }
}*rroot;
int main(){
    //freopen("input.txt","r",stdin);
    int q;
    n=read();
    q=read();
    if (n==1){
        int a,b;
        while (q--){
            read(),read();
            a=read();
            read();
            b=read();
            if (a>b) printf("%d\n",a-b);
            else printf("0\n");
        }
        return 0;
    }
    for (int x=1;x<n;x++) input[x].first=read(),input[x].second=read();
    root=new node(1,n-1);
    rroot=new rnode(1,n-1);
    int a,b,c,d;
    int type;
    stats *res;
    int fin_time;
    while (q--){
        type=read();
        if (type==2){
            a=read();
            b=read();
            c=read();
            d=read();
            if (a<c) res=new stats(root->query(a,c-1));
            else if (c<a) res=new stats(rroot->query(n-a+1,n-c));
            else{
                if (b>d) printf("%d\n",b-d);
                else printf("0\n");
                continue;
            }
            //printf("%lld %lld %lld %lld\n",res->l_time,res->r_time,res->time_used,res->powers_used);
            fin_time=max(b,res->l_time);
            if (b>res->r_time){
                res->powers_used+=b-res->r_time;
                fin_time=res->r_time;
            }
            fin_time+=res->time_used;
            if (d<fin_time){
                res->powers_used+=fin_time-d;
            }
            printf("%lld\n",res->powers_used);
        }
        else{
            a=read();
            b=read();
            c=read();
            input[a]=ii(b,c);
            root->update(a);
            rroot->update(n-a);
        }
    }
}

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