Submission #1164145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164145		Math4Life2020	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	322 ms	91380 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

struct Node {
    ll t1,t2,c,k;
    bool blnk = 0;
    Node(){
        blnk = 1;
    }
    Node(ll l, ll r) {
        t1 = l; t2 = r-1; c=0; k=1;
    }
    pii eval(ll x) { //final time, final cost
        if (x<=t1) {
            return {t1+k,c};
        } else if (x>=t2) {
            return {t2+k,x-t2+c};
        } else {
            return {x+k,c};
        }
    }
    Node(Node n1, Node n2) {
        if (n1.blnk) {
            t1 = n2.t1;
            t2 = n2.t2;
            c = n2.c;
            k = n2.k;
            blnk = n2.blnk; 
        } else if (n2.blnk) {
            t1 = n1.t1;
            t2 = n1.t2;
            c = n1.c;
            k = n1.k;
            blnk = n1.blnk; 
        } else if (n1.t2+n1.k<=n2.t1) {
            t1 = n1.t2;
            t2 = t1;
            pii e1 = n1.eval(t1);
            pii e2 = n2.eval(e1.first);
            k = e2.first-t1;
            c = e2.second+e1.second;
        } else if (n2.t2<=n1.t1+n1.k) {
            t1 = n1.t1;
            t2 = t1;
            pii e1 = n1.eval(t1);
            pii e2 = n2.eval(e1.first);
            k = e2.first-t1;
            c = e2.second+e1.second;
        } else {
            t1 = max(n1.t1,n2.t1-n1.k);
            t2 = min(n1.t2,n2.t2-n1.k);
            pii e1 = n1.eval(t1);
            pii e2 = n2.eval(e1.first);
            k = e2.first-t1;
            c = e2.second+e1.second;
        }
    }
};

const ll Nm = (1LL<<19); const ll E = 19;
Node stf[2*Nm];
Node str[2*Nm];

ll v2(ll x) {
    return __builtin_ctz(x);
}

Node getf(ll a, ll b) {
    if (a>b) {
        return Node();
    } 
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        return Node(stf[(a>>va)+(1<<(E-va))],getf(a+(1<<va),b));
    } else {
        return Node(getf(a,b-(1<<vb)),stf[(b>>vb)+(1<<(E-vb))]);
    }
}

Node getr(ll a, ll b) {
    if (a>b) {
        return Node();
    } 
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        return Node(getr(a+(1<<va),b),str[(a>>va)+(1<<(E-va))]);
    } else {
        return Node(str[(b>>vb)+(1<<(E-vb))],getr(a,b-(1<<vb)));
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,Q; cin >> N >> Q;
    ll l[N-1]; ll r[N-1];
    for (ll i=0;i<(N-1);i++) {
        cin >> l[i] >> r[i];
        stf[i+Nm]=Node(l[i],r[i]);
        str[i+Nm]=Node(l[i],r[i]);
    }
    pii ptest = Node(0,1).eval(3);
    for (ll p=(Nm-1);p>=1;p--) {
        stf[p]=Node(stf[2*p],stf[2*p+1]);
        str[p]=Node(str[2*p+1],str[2*p]);
    }
    for (ll q=0;q<Q;q++) {
        ll t1; cin >> t1;
        if (t1==1) {
            ll i,S1,E1; 
            cin >> i >> S1 >> E1; i--;
            stf[i+Nm]=Node(S1,E1);
            str[i+Nm]=Node(S1,E1);
            for (ll e=1;e<=E;e++) {
                stf[(i+Nm)>>e]=Node(stf[2*((i+Nm)>>e)],stf[1+2*((i+Nm)>>e)]);
                str[(i+Nm)>>e]=Node(str[1+2*((i+Nm)>>e)],str[2*((i+Nm)>>e)]);
            }
        } else {
            ll a,b,c,d; 
            cin >> a >> b >> c >> d; a--; c--;
            if (a<c) {
                Node n1 = getf(a,c-1);
                pii pf = n1.eval(b);
                cout << (pf.second+max(0LL,pf.first-d)) <<"\n";
            } else if (a>c) {
                Node n1 = getr(c,a-1);
                pii pf = n1.eval(b);
                cout << (pf.second+max(0LL,pf.first-d)) <<"\n";
            } else {
                cout << max(0LL,b-d)<<"\n";
            }
        }
    }
}

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