Submission #1171824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171824		M_W_13	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	551 ms	51764 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
const int MAXN = 1 << 19;

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;
        w.czas = a.czas + b.czas - w.travel;
        w.travel += a.travel + b.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;
}

pt seg[2 * MAXN];
pt seg2[2 * MAXN];

void upd(int v, pt x) {
    v += MAXN;
    seg[v] = x;
    v /= 2;
    while (v > 0) {
        seg[v] = polacz(seg[2 * v], seg[2 * v + 1]);
        v /= 2;
    }
}

void upd2(int v, pt x) {
    v += MAXN;
    seg2[v] = x;
    v /= 2;
    while (v > 0) {
        seg2[v] = polacz(seg2[2 * v + 1], seg2[2 * v]);
        v /= 2;
    }
}

pt query(int l, int r) {
    vector<pt> vec1;
    vector<pt> vec2;
    l += MAXN;
    r += MAXN;
    while (l < r) {
        if (l % 2 == 1) {
            vec1.pb(seg[l]);
            l++;
        }
        if (r % 2 == 0) {
            vec2.pb(seg[r]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        vec1.pb(seg[l]);
    }
    vector<pt> vec;
    int sz1 = vec1.size();
    int sz2 = vec2.size();
    reverse(vec2.begin(), vec2.end());
    rep(i, sz1) {
        vec.pb(vec1[i]);
    }
    rep(i, sz2) {
        vec.pb(vec2[i]);
    }
    pt w = vec[0];
    int sz = vec.size();
    for (int i = 1; i < sz; i++) {
        w = polacz(w, vec[i]);
    }
    return w;
}

pt query2(int l, int r) {
    vector<pt> vec1;
    vector<pt> vec2;
    l += MAXN;
    r += MAXN;
    while (l < r) {
        if (l % 2 == 1) {
            vec1.pb(seg2[l]);
            l++;
        }
        if (r % 2 == 0) {
            vec2.pb(seg2[r]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        vec1.pb(seg2[l]);
    }
    vector<pt> vec;
    int sz1 = vec1.size();
    int sz2 = vec2.size();
    reverse(vec1.begin(), vec1.end());
    rep(i, sz2) {
        vec.pb(vec2[i]);
    }
    rep(i, sz1) {
        vec.pb(vec1[i]);
    }
    pt w = vec[0];
    int sz = vec.size();
    for (int i = 1; i < sz; i++) {
        w = polacz(w, vec[i]);
    }
    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;
        upd(i, T[i]);
        upd2(i, T[i]);
    }
    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) {
                pt w = query(a, c - 1);
                w = polacz({b, b, 0, 0}, w);
                ll ans = w.travel + max(0ll, w.czas + w.l - d);
                cout << ans << '\n';
            }
            else if (a > c) {
                pt w = query2(c, a - 1);
                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;
            upd(p, T[p]);
            upd2(p, T[p]);
        }
    }
	return 0;
}

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