Submission #1171823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171823		M_W_13	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	3094 ms	9256 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second

struct pt {
    ll l, r;
    ll czas;
    ll travel;
};

pt polacz(pt a, pt b) {
    pt w;
    b.l -= a.czas;
    b.r -= a.czas;
    if (b.r < a.l) {
        w.travel = a.l - b.r + a.travel + b.travel;
        w.czas = a.czas + b.czas - w.travel;
        w.l = a.l;
        w.r = a.l;
        return w;
    }
    w.l = min(a.r, max(a.l, b.l));
    w.r = max(a.l, min(a.r, b.r));
    w.czas = a.czas + b.czas + max(0ll, b.l - w.r);
    w.travel = a.travel + b.travel;
    return w;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    pt T[n - 1];
    rep(i, n - 1) {
        cin >> T[i].l >> T[i].r;
        T[i].r--;
        T[i].czas = 1ll;
        T[i].travel = 0ll;
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 2) {
            int a, c; ll b, d;
            cin >> a >> b >> c >> d;
            a--;
            c--;
            if (a < c) {
                c--;
                pt w = T[c];
                for (int i = c - 1; i >= a; i--) {
                    w = polacz(T[i], w);
                    // cout << w.l << " " << w.r << " " << w.czas << " " << w.travel << '\n';
                }
                w = polacz({b, b, 0, 0}, w);
                // cout << w.l << " " << w.r << " " << w.czas << " " << w.travel << '\n';
                ll ans = w.travel + max(0ll, w.czas + w.l - d);
                cout << ans << '\n';
            }
            else if (a > c) {
                pt w = T[c];
                for (int i = c + 1; i < a; i++) {
                    w = polacz(T[i], w);
                }
                w = polacz({b, b, 0, 0}, w);
                ll ans = w.travel + max(0ll, w.czas + w.l - d);
                cout << ans << '\n';
            }
            else {
                ll ans = max(0ll, b - d);
                cout << ans << '\n';
            }
        }
        else {
            int p; ll l, r;
            cin >> p >> l >> r;
            p--;
            T[p].l = l;
            T[p].r = r - 1;
            T[p].czas = 1;
            T[p].travel = 0;
        }
    }
	return 0;
}

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