Submission #261175

#	Time	Username	Problem	Language	Result	Execution time	Memory
261175		keko37	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	1582 ms	78344 KiB

timeleap

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 300005;
const llint INF = 1000000000000000000LL;

llint n, q, ofs = 1;
llint lef[MAXN], rig[MAXN];
llint tip[MAXN], A[MAXN], B[MAXN], C[MAXN], D[MAXN], sol[MAXN];

struct node {
    bool konst;
    llint lo, hi, c;
    llint w, h;
    node () {}
} t[MAXN * 4], e;

void ispis (node a) {
    cout << "node" << endl;
    cout << "konst " << a.konst << "  ";
    if (a.konst) cout << a.c; else cout << a.lo << " " << a.hi;
    cout << endl;
    cout << a.w << " " << a.h << endl;
}

llint f (node a, llint x) {
    if (a.konst) return a.c;
    return max(a.lo, min(a.hi, x));
}

llint cost (node a, llint x) {
    return max(x - a.w, 0LL) + a.h;
}

node spoji (node a, node b) {
    if (b.c == -INF) return a;
    if (a.c == -INF) return b;
    node res;
    if (a.konst) {
        res.konst = 1;
        res.c = f(b, a.c);
        res.w = a.w;
        res.h = a.h + cost(b, a.c);
    } else {
        if (b.konst) {
            res.konst = 1;
            res.c = b.c;
        } else if (a.hi < b.lo || b.hi < a.lo) {
            res.konst = 1;
            if (a.hi < b.lo) res.c = b.lo; else res.c = b.hi;
        } else {
            res.konst = 0;
            res.lo = max(a.lo, b.lo);
            res.hi = min(a.hi, b.hi);
        }
        res.h = b.h;
        if (a.lo <= b.w && b.w <= a.hi) {
            res.w = b.w;
        } else if (a.hi < b.w) {
            res.w = a.hi;
        } else {
            res.w = a.lo;
            res.h = cost(b, a.lo);
        }
    }
    return res;
}

void tour_init () {
    e.c = -INF;
    for (int i = 0; i < n-1; i++) {
        t[i + ofs].konst = 0;
        t[i + ofs].lo = lef[i]; t[i + ofs].hi = rig[i];
        t[i + ofs].h = 0;
        t[i + ofs].w = rig[i];
    }
    for (int i = ofs - 1; i > 0; i--) {
        t[i] = spoji(t[2 * i], t[2 * i + 1]);
    }
}

void update (int pos, int lo, int hi) {
    //cout << "update " << pos << "  " << lo << " " << hi << endl;
    pos += ofs;
    t[pos].lo = lo; t[pos].hi = hi; t[pos].w = hi;
    pos /= 2;
    while (pos > 0) {
        t[pos] = spoji(t[pos * 2], t[pos * 2 + 1]);
        pos /= 2;
    }
}

node upit (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return t[x];
    if (to < lo || hi < from) return e;
    return spoji(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

void okreni () {
    reverse(lef, lef + n - 1);
    reverse(rig, rig + n - 1);
    for (int i = 0; i < q; i++) {
        if (tip[i] == 1) {
            A[i] = n - 2 - A[i];
        } else {
            A[i] = n - 1 - A[i];
            C[i] = n - 1 - C[i];
        }
    }
}

void solve_lef_to_rig () {
    for (int i = 0; i < n - 1; i++) lef[i] -= i, rig[i] -= i;
    tour_init();
    for (int i = 0; i < q; i++) {
        if (tip[i] == 1) {
            B[i] -= A[i]; C[i] -= A[i];
            update(A[i], B[i], C[i] - 1);
            B[i] += A[i]; C[i] += A[i];
        } else if (A[i] < C[i]) {
            B[i] -= A[i]; D[i] -= C[i];
            //cout << "upit " << A[i] << " " << C[i] - 1 << endl;
            node res = upit(1, A[i], C[i] - 1, 0, ofs - 1);
            //ispis(res);
            llint val = cost(res, B[i]) + max(f(res, B[i]) - D[i], 0LL);
            sol[i] = val;
            B[i] += A[i]; D[i] += C[i];
        }
    }
    for (int i = 0; i < n - 1; i++) lef[i] += i, rig[i] += i;
}

void solve_const () {
    for (int i = 0; i < q; i++) {
        if (tip[i] == 2 && A[i] == C[i]) {
            sol[i] = max(B[i] - D[i], 0LL);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    while (ofs < n) ofs *= 2;
    for (int i = 0; i < n - 1; i++) {
        cin >> lef[i] >> rig[i];
        rig[i]--;
    }
    for (int i = 0; i < q; i++) {
        cin >> tip[i];
        if (tip[i] == 1) {
            cin >> A[i] >> B[i] >> C[i];
            A[i]--;
        } else {
            cin >> A[i] >> B[i] >> C[i] >> D[i];
            A[i]--; C[i]--;
        }
    }
    solve_lef_to_rig();
    okreni();
    solve_lef_to_rig();
    solve_const();
    for (int i = 0; i < q; i++) {
        if (tip[i] == 2) cout << sol[i] << endl;
    }
    return 0;
}

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