Submission #472375

#	Time	Username	Problem	Language	Result	Execution time	Memory
472375		ITO	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	100 / 100	2301 ms	86260 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};
        return a2;
    }
    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 no, int ql, int qr) {
    if (id < ql || id > qr) {
        return;
    }
    if (ql == qr) {
        mx[no] = {0, 0, v.first, v.second};
        return;
    }
    int m = (ql + qr) / 2;
    upd(v, id, no * 2, ql, m);
    upd(v, id, no * 2 + 1, m + 1, qr);
    mx[no] = merge(mx[no * 2], mx[no * 2 + 1]);
    return;
}
void upd2(pair<ll, ll> v, int id, int no, int ql, int qr) {
    if (id < ql || id > qr) {
        return;
    }
    if (ql == qr) {
        mx2[no] = {0, 0, v.first, v.second};
        return;
    }
    int m = (ql + qr) / 2;
    upd2(v, id, no * 2, ql, m);
    upd2(v, id, no * 2 + 1, m + 1, qr);
    mx2[no] = merge(mx2[no * 2], mx2[no * 2 + 1]);
    return;
}
tcio qry(int l, int r, int no, int ql, int qr) {
    if (l > qr || r < ql) {
        return {0, 0, -1000000001, 1000000001};
    }
    if (ql >= l && qr <= r) {
        return mx[no];
    }
    int m = (ql + qr) / 2;
    return merge(qry(l, r, no * 2, ql, m), qry(l, r, no * 2 + 1, m + 1, qr));
}
tcio qry2(int l, int r, int no, int ql, int qr) {
    if (l > qr || r < ql) {
        return {0, 0, -1000000001, 1000000001};
    }
    if (ql >= l && qr <= r) {
        return mx2[no];
    }
    int m = (ql + qr) / 2;
    return merge(qry2(l, r, no * 2, ql, m), qry2(l, r, no * 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--;
        j = n - i - 1;
        upd(mp(la - i, ra - i), i, 1, 0, n - 1);
        upd2(mp(la - j, ra - j), j, 1, 0, n - 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, n - 1);
            upd2(mp(s - j, e - j), j, 1, 0, n - 1);
        } 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, n - 1)), {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, n - 1)), {0, 0, tb, tb});
            }
            cout << ab.c << '\n';
        }
    }
    return 0;
}

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