Submission #708776

#	Time	Username	Problem	Language	Result	Execution time	Memory
708776		alvingogo	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	446 ms	123980 KiB

timeleap

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const int inf=1e9;
vector<pair<int,int> > gg[2];
struct ST{
    int tp;
    struct no{
        int ax,ay,bx;
        // <=ax : ay
        // >=bx : by=bx+(ay-ax)
        int dx,dy;
        // <=dx : dy
        // >=dx : linear 
    };
    vector<no> st;
    pair<int,int> get(no& a,int x){
        pair<int,int> ret;
        if(x<=a.ax){
            ret.fs=a.ay;
        }
        else if(x>=a.bx){
            ret.fs=a.bx+a.ay-a.ax;
        }
        else{
            ret.fs=a.ay+(x-a.ax);
        }
        if(x<=a.dx){
            ret.sc=a.dy;
        }
        else{
            ret.sc=a.dy+x-a.dx;
        }
        return ret;
    }
    void upd(int v,int l,int r){
        st[v].ax=l;
        st[v].ay=l+1;
        st[v].bx=r;
        st[v].dx=r;
        st[v].dy=0;
    }
    void pull(int v){
        auto p=st[2*v+1],q=st[2*v+2];
        if(get(q,p.ay).fs==get(q,p.bx+p.ay-p.ax).fs){
            st[v].ax=st[v].bx=0;
            st[v].ay=get(q,p.ay).fs;
        }
        else{
            st[v].ax=p.ax+max(0ll,q.ax-p.ay);
            st[v].ay=get(q,get(p,st[v].ax).fs).fs;
            st[v].bx=p.bx-max(0ll,p.bx+p.ay-p.ax-q.bx);
        }
        int c=get(p,0).sc+get(q,get(p,0).fs).sc,d=get(p,inf).sc+get(q,get(p,inf).fs).sc;
        st[v].dx=inf-(d-c);
        st[v].dy=c;
    }
    void build(int v,int L,int R){
        if(L==R){
            upd(v,gg[tp][L].fs,gg[tp][L].sc);
            return;
        }  
        int m=(L+R)/2;
        build(2*v+1,L,m);
        build(2*v+2,m+1,R);
        pull(v);
    }
    void print(int v){
        cout << v << ":" << "\n";
        cout << st[v].ax << " " << st[v].ay << " " << st[v].bx << "\n";
        cout << st[v].dx << " " << st[v].dy << "\n\n";
    }
    void init(int x){
        st.resize(4*x);
        build(0,0,x-1);
    }
    void update(int v,int L,int R,int p,int l,int r){
        if(L==R){
            upd(v,l,r);
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,l,r);
        }
        else{
            update(2*v+2,m+1,R,p,l,r);
        }
        pull(v);
    }
    pair<int,int> query(int v,int L,int R,int l,int r,int x){
        if(L==l && R==r){
            return get(st[v],x);
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r,x);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r,x);
        }
        else{
            auto h=query(2*v+1,L,m,l,m,x);
            auto y=query(2*v+2,m+1,R,m+1,r,h.fs);
            return {y.fs,y.sc+h.sc};
        }
    }
}st[2];
signed main(){
    AquA;
    int n,q;
    cin >> n >> q;
    n--;
    gg[0].resize(n);
    gg[1].resize(n);
    for(int i=0;i<n;i++){
        cin >> gg[0][i].fs >> gg[0][i].sc;
        gg[0][i].sc--;
    }
    gg[1]=gg[0];
    reverse(gg[1].begin(),gg[1].end());
    st[0].tp=0;
    st[1].tp=1;
    st[0].init(n);
    st[1].init(n);
    for(int i=0;i<4*n;i++){
        //st[1].print(i);
    }
    //cout << st.st[0].ax << " " << st.st[0].ay << " " << st.st[0].bx << " " << st.st[0].dx << " " << st.st[0].dy << '\n';
    //cout << st.get(st.st[0],3).fs << " " << st.get(st.st[0],3).sc << "\n";
    for(int i=0;i<q;i++){
        int t;
        cin >> t;
        if(t==1){
            int a,l,r;
            cin >> a >> l >> r;
            a--;
            r--;
            st[0].update(0,0,n-1,a,l,r);
            st[1].update(0,0,n-1,n-a-1,l,r);
        }
        else{
            int a,b,c,d;
            cin >> a >> b >> c >> d;
            if(a==c){
                cout << max(0ll,b-d) << "\n";
                continue;
            }
            if(a<c){
                a--;
                c--;
                c--;
                auto h=st[0].query(0,0,n-1,a,c,b);
                cout << h.sc+(max(0ll,h.fs-d)) << "\n";
            }
            else{
                a--;
                c--;
                a=n-a;
                c=n-c;
                c--;
                //cout << a << " " << c << endl;
                auto h=st[1].query(0,0,n-1,a,c,b);
                cout << h.sc+(max(0ll,h.fs-d)) << "\n";
            }
        }
    }
    return 0;
}

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