Submission #472348

#	Time	Username	Problem	Language	Result	Execution time	Memory
472348		ITO	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	0 / 100	1773 ms	70248 KiB

timeleap

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
struct tcio {
    bool t;
    ll c, i, o;
} mx[1048576], mx2[1048576], ab;
tcio merge(tcio a1, tcio a2) {
    if (a1.t == 0) {
        if (a2.t == 0) {
            if (a1.i > a2.o) return {1, a1.i - a2.o, a1.i, a2.o};
            if (a1.o < a2.i)  return {1, 0ll, a1.o, a2.i};
            return {0, 0ll, max(a1.i, a2.i), min(a1.o, a2.o)};
        }
        if (a2.i < a1.i) return {1, a1.i - a2.i + a2.c, a1.i, a2.o};
        if (a2.i > a1.o) return {1, a2.c, a1.o, a2.o};
    }
    if (a2.t == 0) {
        if (a1.o < a2.i) return {1, a1.c, a1.i, a2.i};
        if (a1.o > a2.o) return {1, a1.o - a2.o + a1.c, a1.i, a2.o};
        return {1, a1.c, a1.i, a1.o};
    }
    return {1, max(a1.o - a2.i, 0ll) + a1.c + a2.c, a1.i, a2.o};
}
void upd(pair<ll, ll> v, int id, int n, int ql, int qr) {
    if (id < ql || id > qr) {
        return;
    }
    if (ql == qr) {
        mx[n] = {0, 0, v.first, v.second};
        return;
    }
    int m = (ql + qr) / 2;
    upd(v, id, n * 2, ql, m);
    upd(v, id, n * 2 + 1, m + 1, qr);
    mx[n] = merge(mx[n * 2], mx[n * 2 + 1]);
    return;
}
void upd2(pair<ll, ll> v, int id, int n, int ql, int qr) {
    if (id < ql || id > qr) {
        return;
    }
    if (ql == qr) {
        mx2[n] = {0, 0, v.first, v.second};
        return;
    }
    int m = (ql + qr) / 2;
    upd2(v, id, n * 2, ql, m);
    upd2(v, id, n * 2 + 1, m + 1, qr);
    mx2[n] = merge(mx2[n * 2], mx2[n * 2 + 1]);
    return;
}
tcio qry(int l, int r, int n, int ql, int qr) {
    if (l > qr || r < ql) {
        return {0, 0, -1000000001, 1000000001};
    }
    if (ql >= l && qr <= r) {
        return mx[n];
    }
    int m = (ql + qr) / 2;
    return merge(qry(l, r, n * 2, ql, m), qry(l, r, n * 2 + 1, m + 1, qr));
}
tcio qry2(int l, int r, int n, int ql, int qr) {
    if (l > qr || r < ql) {
        return {0, 0, -1000000001, 1000000001};
    }
    if (ql >= l && qr <= r) {
        return mx2[n];
    }
    int m = (ql + qr) / 2;
    return merge(qry2(l, r, n * 2, ql, m), qry2(l, r, n * 2 + 1, m + 1, qr));
}
int main(){
    int n, q, j, la, ra, t, p, s, e, ca, ta, cb, tb;
    cin >> n >> q;
    n--;
    for (int i = 0; i < n; i++) {
        cin >> la >> ra;
        ra--;
        mx[i + 524288].i = la - i;
        mx[i + 524288].o = ra - i;
        j = n - i - 1;
        mx2[j + 524288].i = la - j;
        mx2[j + 524288].o = ra - j;
    }
    for (int i = n + 524288; i < 1048576; i++) {
        mx[i].i = -1000000001;
        mx[i].o = 1000000001;
        mx2[i].i = -1000000001;
        mx2[i].o = 1000000001;
    }
    for (int i = 524287; i > 0; i--) {
        mx[i] = merge(mx[i * 2], mx[i * 2 + 1]);
        mx2[i] = merge(mx2[i * 2], mx2[i * 2 + 1]);
    }
    for (int i = 0; i < q; i++) {
        cin >> t;
        if (t == 1) {
            cin >> p >> s >> e;
            p--, e--, j = n - p - 1;
            upd(mp(s - p, e - p), p, 1, 0, 524287);
            upd2(mp(s - j, e - j), j, 1, 0, 524287);
        } else {
            cin >> ca >> ta >> cb >> tb;
            ca--, cb--, tb--;
            if (ca <= cb) {
                cb--, ta -= ca, tb -= cb;
                ab = merge(merge({0, 0, ta, ta}, qry(ca, cb, 1, 0, 524287)), {0, 0, tb, tb});
            } else {
                ca = n - ca, cb = n - cb, cb--, ta -= ca, tb -= cb;
                ab = merge(merge({0, 0, ta, ta}, qry2(ca, cb, 1, 0, 524287)), {0, 0, tb, tb});
            }
            cout << ab.c << '\n';
        }
    }
    return 0;
}

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