Submission #1306627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306627		jwpassion1	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	388 ms	91236 KiB

timeleap

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

struct Node {
    pair<ll, ll> lin, lout;
    ll ldp;
};

void merge(Node& ret, Node& l, Node& r) {
    ret.lin = l.lin;
    ret.lout = l.lout;
    ret.ldp = l.ldp + r.ldp;

    if (ret.lin.first < ret.lin.second) {
        if (ret.lout.second <= r.lin.first) {
            ret.lin.first = ret.lin.second;
            ret.lout.first = ret.lout.second;
        }
        else if (ret.lout.first >= r.lin.second) {
            ret.lin.second = ret.lin.first;
            ret.lout.second = ret.lout.first;
        }
        else {
            if (ret.lout.first < r.lin.first) {
                ret.lin.first += r.lin.first - ret.lout.first;
                ret.lout.first = r.lin.first;
            }
            if (ret.lout.second > r.lin.second) {
                ret.lin.second += r.lin.second - ret.lout.second;
                ret.lout.second = r.lin.second;
            }
            if (ret.lin.first < ret.lin.second) {
                ret.lout.first += r.lout.first - r.lin.first;
                ret.lout.second += r.lout.first - r.lin.first;
            }
        }
    }

    if (ret.lin.first == ret.lin.second) {
        if (ret.lout.first > r.lin.second) ret.ldp += ret.lout.first - r.lin.second;
        if (r.lin.first < r.lin.second) {
            if (ret.lout.first > r.lin.second) ret.lout.first = ret.lout.second = r.lin.second;
            else if (ret.lout.second < r.lin.first) ret.lout.first = ret.lout.second = r.lin.first;
            ret.lout.first += r.lout.first - r.lin.first;
            ret.lout.second += r.lout.first - r.lin.first;
        }
        else ret.lout = r.lout;
    }
}

ll L[300000], R[300000];
Node lseg[1048576], rseg[1048576];

void init(int t1, int t2, int idx) {
    if (t1 == t2) {
        lseg[idx].lin = rseg[idx].lin = {L[t1], R[t1]};
        lseg[idx].lout = rseg[idx].lout = {L[t1] + 1, R[t1] + 1};
        lseg[idx].ldp = rseg[idx].ldp = 0;
        return;
    }
    int mid = (t1 + t2) >> 1;
    init(t1, mid, idx << 1);
    init(mid + 1, t2, idx << 1 | 1);
    merge(lseg[idx], lseg[idx << 1], lseg[idx << 1 | 1]);
    merge(rseg[idx], rseg[idx << 1 | 1], rseg[idx << 1]);
}

void update(int t1, int t2, int q, int idx) {
    if (q < t1 || t2 < q) return;
    if (t1 == t2) {
        lseg[idx].lin = rseg[idx].lin = {L[t1], R[t1]};
        lseg[idx].lout = rseg[idx].lout = {L[t1] + 1, R[t1] + 1};
        return;
    }
    int mid = (t1 + t2) >> 1;
    update(t1, mid, q, idx << 1);
    update(mid + 1, t2, q, idx << 1 | 1);
    merge(lseg[idx], lseg[idx << 1], lseg[idx << 1 | 1]);
    merge(rseg[idx], rseg[idx << 1 | 1], rseg[idx << 1]);
}

Node query(int t1, int t2, int q1, int q2, bool isl, int idx) {
    if (q1 <= t1 && t2 <= q2) return isl ? lseg[idx] : rseg[idx];
    int mid = (t1 + t2) >> 1;
    if (q2 <= mid) return query(t1, mid, q1, q2, isl, idx << 1);
    if (mid + 1 <= q1) return query(mid + 1, t2, q1, q2, isl, idx << 1 | 1);
    Node l = query(t1, mid, q1, q2, isl, idx << 1), r = query(mid + 1, t2, q1, q2, isl, idx << 1 | 1);
    Node ret;
    isl ? merge(ret, l, r) : merge(ret, r, l);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N - 1; i++) {
        cin >> L[i] >> R[i];
        R[i]--;
    }

    if (N == 1) {
        while (Q--) {
            int T;
            cin >> T;
            if (T == 1) {
                int P;
                ll S, E;
                cin >> P >> S >> E;
            }
            else {
                int A, C;
                ll B, D;
                cin >> A >> B >> C >> D;
                if (B <= D) cout << "0\n";
                else cout << B - D << '\n';
            }
        }
        return 0;
    }

    init(0, N - 2, 1);

    while (Q--) {
        int T;
        cin >> T;
        if (T == 1) {
            int P;
            ll S, E;
            cin >> P >> S >> E;
            L[--P] = S;
            R[P] = E - 1;
            update(0, N - 2, P, 1);
        }
        else {
            int A, C;
            ll B, D;
            cin >> A >> B >> C >> D;
            if (--A == --C) {
                if (B <= D) cout << "0\n";
                else cout << B - D << '\n';
            }
            else {
                Node qval = query(0, N - 2, min(A, C), max(A, C) - 1, A < C, 1);
                //cout << qval.lin.first << ' ' << qval.lin.second << " -> " << qval.lout.first << ' ' << qval.lout.second << " = " << qval.ldp << '\n';
                ll ans = qval.ldp;
                if (B > qval.lin.second) {
                    ans += B - qval.lin.second;
                    B = qval.lin.second;
                }
                else if (B < qval.lin.first) B = qval.lin.first;
                B += qval.lout.first - qval.lin.first;
                if (B > D) ans += B - D;
                cout << ans << '\n';
            }
        }
    }
}

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