Submission #718151

#	Time	Username	Problem	Language	Result	Execution time	Memory
718151		walterw	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	658 ms	86312 KiB

timeleap

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

struct statt {
    int lb, rb, time_wait, power_used;
};

statt comb(statt lc, statt rc) {
    statt res;

    int delta = lc.time_wait - lc.power_used;
    int newl = lc.lb + delta, newr = lc.rb + delta;

    res.time_wait = lc.time_wait + rc.time_wait;
    res.power_used = lc.power_used + rc.power_used;

    if (max(newl, rc.lb) <= min(newr, rc.rb)) {
        res.lb = max(newl, rc.lb) - delta;
        res.rb = min(newr, rc.rb) - delta;
    } else if (newr < rc.lb) {
        res.time_wait += (rc.lb - newr);
        res.lb = res.rb = lc.rb;
    } else {
        res.power_used += (newl - rc.rb);
        res.lb = res.rb = lc.lb;
    }

    return res;
}

struct segtree {


    statt tree[4 * 300005];

    void update(int x, int l, int r, int id, int ul, int ur) {
        if (l == r) {
            tree[x] = {ul, ur, 0, 0};
            return;
        }

        int mid = (l + r) / 2;

        if (id <= mid) update(2 * x, l, mid, id, ul, ur);
        else update(2 * x + 1, mid + 1, r, id, ul, ur);

        tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
    }

    statt query(int x, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[x];
        if (l > qr || ql > r) return {(int) -2e16, (int) 2e16, 0, 0};

        int mid = (l + r) / 2;

        return comb(query(2 * x, l, mid, ql, qr), query(2 * x + 1, mid + 1, r, ql, qr));
    }
};

segtree seg1, seg2;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, q; cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int l, r; cin >> l >> r;
        int newl= l - i;
        int newr = r - (i + 1);
        seg1.update(1, 1, n, i, newl, newr);

        newl = l - ((n - i));
        newr = r - ((n - i) + 1);

        seg2.update(1, 1, n, (n - i), newl, newr);
    }

    while (q--){
        int t; cin >> t;
        if (t == 1) {
            int p, s, e; cin >> p >> s >> e;

            int newl = s - p;
            int newr = e - (p + 1);
            seg1.update(1, 1, n, p, newl, newr);

            newl = s - ((n - p));
            newr = e - ((n - p) + 1);

            seg2.update(1, 1, n, (n - p), newl, newr);
        } else {
            int a, b, c, d; cin >> a >> b >> c >> d;

            if (a < c) {
                statt interval = seg1.query(1, 1, n, a, c - 1);

                b -= a;
                d -= (c);

                int start_time = max(b, interval.lb);
                if (b > interval.rb) {
                    interval.power_used += (b - interval.rb);
                }

                start_time += interval.time_wait;
                start_time -= interval.power_used;

                if (start_time > d) {
                    interval.power_used += start_time - d;
                }

                cout << interval.power_used << "\n";
            } else if (a > c) {
                statt interval = seg2.query(1, 1, n, n - a + 1, n - c);

                b = b - ( n - a + 1);
                d = (d) - (n - c + 1);

                int start_time = max(b, interval.lb);
                if (b > interval.rb) {
                    interval.power_used += (b - interval.rb);
                }

                start_time += interval.time_wait;
                start_time -= interval.power_used;

                if (start_time > d) {
                    interval.power_used += start_time - d;
                }

                cout << interval.power_used << "\n";
            } else {
                if (b < d) {
                    cout << "0\n";
                } else {
                    cout << b - d << "\n";
                }
            }
        }
    }

}

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