Submission #894067

#	Time	Username	Problem	Language	Result	Execution time	Memory
894067		box	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	709 ms	524288 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

int N, Q;

struct info {
    // z = -1 => intersection between all intervals is positive, stored in [x, y]
    // z >= 0 => z stores cost, x is maximum starting point, y is minimum ending point (under minimum cost)
    int x, y;
    i64 z;
    void pr() const {
        cout << "{x=" << x << ", y=" << y << ", z=" << z << "}";
    }
};
info operator+(const info one, const info two) {
    if (~one.z && ~two.z) return {one.x, two.y, one.z + two.z + max(0, one.y - two.x)};
    if (~one.z) return {one.x, one.y < two.x ? two.x : min(one.y, two.y), one.z + max(0, one.y - two.y)};
    if (~two.z) return {two.x > one.y ? one.y : max(one.x, two.x), two.y, two.z + max(0, one.x - two.x)};
    // cout << "\t merging "; one.pr(); cout << " and "; two.pr(); cout << '\n';
    // cout << "last case" << endl;
    if (max(one.x, two.x) <= min(one.y, two.y)) return {max(one.x, two.x), min(one.y, two.y), -1};
    return one.y < two.x ? info{one.y, two.x, 0} : info{one.x, two.y, one.x - two.y};
}

struct segt {
    int l, r;
    segt *lc = NULL, *rc = NULL;
    info x;
    segt(int l, int r) : l(l), r(r) {
        if (l == r) x = info{-1, -1, -1};
        else {
            int m = (l + r) / 2;
            lc = new segt(l, m), rc = new segt(m + 1, r);
            x = lc->x + rc->x;
        }
    }
    void upd(int i, int ql, int qr) {
        if (l == r) x = {ql - l, qr - l - 1, -1};
        else {
            i <= lc->r ? lc->upd(i, ql, qr) : rc->upd(i, ql, qr);
            x = lc->x + rc->x;
        }
        // cout << "GOT " << l << ' ' << r << ": ";
        // x.pr();
        // cout << '\n';
    }
    info qry(int ql, int qr) {
        if (ql <= l && qr >= r) return x;
        if (qr <= lc->r) return lc->qry(ql, qr);
        if (ql >= rc->l) return rc->qry(ql, qr);
        return lc->qry(ql, qr) + rc->qry(ql, qr);
    }
} *tree, *tree_rev;

void upd(int i, int l, int r) {
    tree->upd(i, l, r);
    tree_rev->upd(N - i - 1, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> Q, N--;
    tree = new segt(0, N - 1);
    tree_rev = new segt(0, N - 1);
    for (int i = 0; i < N; i++) {
        int l, r;
        cin >> l >> r;
        upd(i, l, r);
    }
    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, l, r;
            cin >> i >> l >> r, i--;
            upd(i, l, r);
        } else {
            int i, t1, j, t2;
            cin >> i >> t1 >> j >> t2, i--, j--;
            if (i == j)
                cout << max(0, t1 - t2) << '\n';
            else if (i < j) {
                info one{t1 - i, t1 - i, -1}, two{t2 - j, t2 - j, -1};
                // info mid{tree->qry(i, j - 1)};
                // cout << "one: "; one.pr(); cout << '\n';
                // cout << "two: "; two.pr(); cout << '\n';
                // cout << "mid: "; mid.pr(); cout << '\n';
                // cout << "one+mid: "; (one+mid).pr(); cout << '\n';
                cout << max(i64(0), (one + tree->qry(i, j - 1) + two).z) << '\n';
            } else {
                i = N - i;
                j = N - j;
                info one{t1 - i, t1 - i, -1}, two{t2 - j, t2 - j, -1};
                cout << max(i64(0), (one + tree_rev->qry(i, j - 1) + two).z) << '\n';
            }
        }
    }
}

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