Submission #1131625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131625		elush	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	34 / 100	463 ms	47936 KiB

timeleap

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
//#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;

const int MAX_N = 3e5 + 5;
const ll infinity = 1e9;

struct PosFunction {
    //g(t) = max(l, min(r, t))
    ll l = 0, r = 0;
    PosFunction() {}
    PosFunction(ll l, ll r): l(l), r(r) {}
    ll operator()(ll t) {
        return max(l, min(r, t));
    }
    PosFunction operator()(PosFunction g) {
        if (r < g.l) return {r, r};
        else if (g.r < l) return {l, l};
        return {max(l, g.l), min(r, g.r)};
    }
};

struct TimeFunction {
    //f(t) = max(a, b + t)
    ll a = 0, b = 0;
    TimeFunction() {}
    TimeFunction(ll a, ll b): a(a), b(b) {}
    ll operator()(ll t) {
        return max(a, b + t);
    }
    TimeFunction operator()(TimeFunction f, PosFunction g) {
        ll a2 = f(0) + (*this)(g(0));
        ll b2 = f(infinity) + (*this)(g(infinity)) - infinity;
        return {a2, b2};
    }
};

struct Seg {
    int n;
    vector<TimeFunction> tim;
    vector<PosFunction> pos;
    Seg() {}
    Seg(int m) {
        for (n = 1; n < m; n <<= 1);
        tim.resize(2 * n), pos.resize(2 * n);
    }
    void Pull(int i) {
        tim[i] = tim[i << 1 | 1](tim[i << 1], pos[i << 1]);
        pos[i] = pos[i << 1 | 1](pos[i << 1]);
    }
    void Update(int i, int l1, int r1, int ind, int a, int b) {
        if (a + 1 == b) {
            pos[ind] = PosFunction(l1, r1);
            tim[ind] = TimeFunction(0, -r1);
            return;
        }
        if (i < ((a + b) >> 1)) Update(i, l1, r1, ind << 1, a, (a + b) >> 1);
        else Update(i, l1, r1, ind << 1 | 1, (a + b) >> 1, b);
        Pull(ind);
    }
    ll Query(int l, int r, ll st, ll et) {
        if (l == r) return max<ll>(0, st - et);
        vi indl, indr;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) indl.push_back(l++);
            if (r & 1) indr.push_back(--r);
        }
        while (!indl.empty()) indr.push_back(indl.back()), indl.pop_back();
        PosFunction p = pos[indr.back()];
        TimeFunction t = tim[indr.back()];
        indr.pop_back();
        while (!indr.empty()) {
            int i = indr.back();
            indr.pop_back();
            t = tim[i](t, p);
            p = pos[i](p);
        }
        ll ans = t(st), po = p(st);
        return ans + max<ll>(0, po - et);
    }
};

int L[MAX_N], R[MAX_N], t[MAX_N], a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];

ll ans[MAX_N];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i + 1 < n; i++) cin >> L[i] >> R[i];
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> a[i] >> b[i] >> c[i];
        if (t[i] == 2) cin >> d[i];
    }
    for (int i = 0; i < q; i++) a[i]--, c[i]--;
    for (int i = 0; i + 1 < n; i++) R[i]--;
    for (int ti = 0; ti < 2; ti++) {
        Seg seg(n);
        for (int i = 0; i + 1 < n; i++) {
            seg.Update(i, L[i] - i, R[i] - i, 1, 0, seg.n);
        }
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                seg.Update(a[i], b[i] - a[i], c[i] - a[i], 1, 0, seg.n);
            } else {
                if (a[i] <= c[i]) ans[i] = seg.Query(a[i], c[i], b[i] - a[i], d[i] - c[i]);
            }
        }
        reverse(L, L + n - 1), reverse(R, R + n - 1);
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) a[i] = n - 2 - a[i];
            else a[i] = n - 1 - a[i], c[i] = n - 1 - c[i];
        }
    }
    for (int i = 0; i < q; i++) {
        if (t[i] == 2) cout << ans[i] << '\n';
    }
}

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