Submission #472374

#	Time	Username	Problem	Language	Result	Execution time	Memory
472374		ITO	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	0 / 100	3057 ms	5216 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;
} ab;
int la[300001], ra[300001], la2[300001], ra2[300001];
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};
}
int main(){
    int n, q, j, t, p, s, e, ca, ta, cb, tb;
    cin >> n >> q;
    n--;
    for (int i = 0; i < n; i++) {
        cin >> la[i] >> ra[i];
        ra[i]--;
        j = n - i - 1;
        la2[j] = la[i] - j;
        ra2[j] = ra[i] - j;
        la[i] -= i;
        ra[i] -= i;;
    }
    for (int i = 0; i < q; i++) {
        cin >> t;
        if (t == 1) {
            cin >> p >> s >> e;
            p--, e--, j = n - p - 1;
            la[p] = s - p;
            ra[p] = e - p;
            la2[j] = s - j;
            ra2[j] = e - j;
        } else {
            cin >> ca >> ta >> cb >> tb;
            ca--, cb--, tb--;
            ab = {0, 0, -1000000001, 1000000001};
            if (ca <= cb) {
                cb--, ta -= ca, tb -= cb;
                ab = {0, 0, ta, ta};
                for (int k = ca; k <= cb; k++) {
                    ab = merge(ab, {0, 0, la[k], ra[k]});
                }
                ab = merge(ab, {0, 0, tb, tb});
            } else {
                ca = n - ca, cb = n - cb, cb--, ta -= ca, tb -= cb;
                ab = {0, 0, ta, ta};
                for (int k = cb; k >= ca; k--) {
                    ab = merge(ab, {0, 0, la[k], ra[k]});
                }
                ab = merge(ab, {0, 0, tb, tb});
            }
            cout << ab.c << '\n';
        }
    }
    return 0;
}

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