Submission #1308498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308498		Hamed_Ghaffari	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	804 ms	111452 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define X first
#define Y second
#define mins(a, b) (a = min(a,b))
#define SZ(x) int(x.size())
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

template<typename T> pair<T, T> operator+(pair<T, T> x, pair<T, T> y) {
    return pair<T, T>(x.X+y.X, x.Y+y.Y);
}

const int MXN = 3e5+5;

int n;

namespace BG {
    int seg[MXN<<2];
    void upd(int p, int x, int l=1, int r=n, int id=1) {
        if(r-l == 1) {
            seg[id] = x;
            return;
        }
        p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
        seg[id] = max(seg[lc], seg[rc]);
    }
    int fir(int s, int x, int l=1, int r=n, int id=1) {
        if(r<=s || seg[id]<=x) return n;
        if(r-l == 1) return l;
        int res = fir(s, x, l, mid, lc);
        return res==n ? fir(s, x, mid, r, rc) : res;
    }
}

namespace LW {
    int seg[MXN<<2];
    void upd(int p, int x, int l=1, int r=n, int id=1) {
        if(r-l == 1) {
            seg[id] = x;
            return;
        }
        p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
        seg[id] = min(seg[lc], seg[rc]);
    }
    int fir(int s, int x, int l=1, int r=n, int id=1) {
        if(r<=s || seg[id]>=x) return n;
        if(r-l == 1) return l;
        int res = fir(s, x, l, mid, lc);
        return res==n ? fir(s, x, mid, r, rc) : res;
    }
}

struct node {
    pll sl, sr;
    pii sg, s1, s2;
    bool h2, h3;
} seg[MXN<<2];

inline node leaf(pii sg) {
    node z;
    z.sl = z.sr = pll(0, 0);
    z.sg = z.s1 = sg;
    z.h2 = z.h3 = 0;
    return z;
}

inline pll merge(ll cur, node y) {
    if(cur<y.s1.X) return y.sl + pll(0, y.sg.X-cur);
    if(cur>y.s1.Y) return y.sr + pll(cur-y.sg.Y, 0);
    if(!y.h2) return pll(0, 0);
    if(y.s2.Y<y.s1.X) return y.sr + pll(cur-y.sg.Y, 0);
    return y.sl + pll(0, y.sg.X-cur);
}

inline node merge(node x, node y) {
    node z;
    z.sg = x.sg;
    if(!x.h2) {
        if(max(x.s1.X, y.s1.X)<=min(x.s1.Y, y.s1.Y)) {
            z.s1 = pii(max(x.s1.X, y.s1.X), min(x.s1.Y, y.s1.Y));
            z.s2 = y.s2; z.h2 = y.h2;
            z.h3 = y.h3;
        }
        else {
            z.s1 = x.s1;
            z.s2 = y.s1; z.h2 = 1;
            z.h3 = y.h2;
        }
    }
    else if(!x.h3) {
        z.s1 = x.s1;
        z.h2 = 1;
        if(max(x.s2.X, y.s1.X)<=min(x.s2.Y, y.s1.Y)) {
            z.s2 = pii(max(x.s2.X, y.s1.X), min(x.s2.Y, y.s1.Y));
            z.h3 = y.h2;
        }
        else {
            z.s2 = x.s2;
            z.h3 = 1;
        }
    }
    else {
        z.s1 = x.s1;
        z.s2 = x.s2; z.h2 = x.h2;
        z.h3 = x.h3;
    }

    z.sl = x.sl + merge(x.sg.X - x.sl.X + x.sl.Y, y);
    z.sr = x.sr + merge(x.sg.Y - x.sr.X + x.sr.Y, y);

    return z;
}

int L[MXN], R[MXN];

void build(int l=1, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = leaf(pii(L[l], R[l]));
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}
void upd(int p, pii x, int l=1, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = leaf(x);
        return;
    }
    p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
    seg[id] = merge(seg[lc], seg[rc]);
}
node get(int s, int e, int l=1, int r=n, int id=1) {
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return merge(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int Lin[MXN], Rin[MXN], q;
vector<int> Q[MXN];
ll ans[MXN];

void solve() {
    for(int i=1; i<n; i++) {
        L[i] = Lin[i]-i;
        R[i] = Rin[i]-i-1;
        BG::upd(i, L[i]);
        LW::upd(i, R[i]);
    }
    build();
    for(int i=1; i<=q; i++)
        if(Q[i][0]==1) {
            BG::upd(Q[i][1], Q[i][2]-Q[i][1]);
            LW::upd(Q[i][1], Q[i][3]-Q[i][1]-1);
            upd(Q[i][1], pii(Q[i][2]-Q[i][1], Q[i][3]-Q[i][1]-1));
        }
        else if(Q[i][1]==Q[i][3]) ans[i] = max(0, Q[i][2]-Q[i][4]);
        else if(Q[i][1]<Q[i][3]) {
            ll a = Q[i][1], b = Q[i][2]-a, c = Q[i][3], d = Q[i][4]-c;
            int pl = BG::fir(a, b), pr = LW::fir(a, b), pos = min(pl, pr);
            if(pos>=c) {
                ans[i] = max(0ll, b-d);
                continue;
            }
            pll x = pos==pl 
                  ? get(pos, c).sl + pll(0, get(pos, pos+1).sg.X - b)
                  : get(pos, c).sr + pll(b - get(pos, pos+1).sg.Y, 0);
            b += x.Y - x.X;
            ans[i] = x.X + max(0ll, b-d);
        }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    if(n==1) {
        while(q--) {
            int t;
            cin >> t;
            if(t==1) cin >> t >> t >> t;
            else {
                int b, d;
                cin >> t >> b >> t >> d;
                cout << max(0, b-d) << '\n';
            }
        }
        return 0;
    }

    for(int i=1; i<n; i++) cin >> Lin[i] >> Rin[i];
    for(int i=1; i<=q; i++) {
        int t;
        cin >> t;
        if(t==1) {
            Q[i].resize(4, t);
            for(int j=1; j<4; j++) cin >> Q[i][j];
        }
        else {
            Q[i].resize(5, t);
            for(int j=1; j<5; j++) cin >> Q[i][j];
        }
    }

    solve();
    reverse(Lin+1, Lin+n);
    reverse(Rin+1, Rin+n);
    for(int i=1; i<=q; i++)
        if(Q[i][0]==1)
            Q[i][1] = n - Q[i][1];
        else
            Q[i][1] = n+1 - Q[i][1],
            Q[i][3] = n+1 - Q[i][3];
    solve();

    for(int i=1; i<=q; i++)
        if(Q[i][0]==2)
            cout << ans[i] << '\n';

    return 0;
}

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