oj.uz

Submission #718149

# Submission time Handle Problem Language Result Execution time Memory
718149 2023-04-03T12:47:24 Z walterw Bitaro, who Leaps through Time (JOI19_timeleap) C++17
4 / 100
 113 ms 61868 KB 
#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 * 200005];

    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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 472 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 476 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 476 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 472 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 472 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 508 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 2 ms 468 KB Output is correct
35 Correct 2 ms 472 KB Output is correct
36 Correct 2 ms 468 KB Output is correct
37 Correct 2 ms 476 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 2 ms 468 KB Output is correct
40 Correct 2 ms 468 KB Output is correct
41 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 61868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 472 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 476 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 476 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 472 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 472 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 508 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 2 ms 468 KB Output is correct
35 Correct 2 ms 472 KB Output is correct
36 Correct 2 ms 468 KB Output is correct
37 Correct 2 ms 476 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 2 ms 468 KB Output is correct
40 Correct 2 ms 468 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Runtime error 113 ms 61868 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -