oj.uz

Submission #871701

# Submission time Handle Problem Language Result Execution time Memory
871701 2023-11-11T10:42:58 Z vjudge1 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
4 / 100
 3000 ms 13236 KB 
#include <bits/stdc++.h>
using namespace std;

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, q;
        cin >> n >> q;
        vector<int> l(n - 1), r(n - 1);
        vector<int> la(n - 1), ra(n - 1);
        vector<int> lb(n - 1), rb(n - 1);
        for (int i = 0; i < n - 1; i++) cin >> l[i] >> r[i], r[i]--;
        for (int i = 0; i < n - 1; i++) la[i] = l[i] - i, ra[i] = r[i] - i;
        for (int i = 0; i < n - 1; i++) lb[i] = l[i] + i, rb[i] = r[i] + i;

        while (q--) {
                int _;
                cin >> _;
                if (_ == 1) {
                        int i;
                        cin >> i;
                        i--;
                        int s, t;
                        cin >> s >> t;
                        t--;
                        la[i] = s - i, ra[i] = t - i;
                        lb[i] = s + i, rb[i] = t + i;
                } else {
                        int a, b, c, d;
                        cin >> a >> b >> c >> d;
                        a--, c--;
                        auto& L = a <= c ? la : lb;
                        auto& R = a <= c ? ra : rb;

                        int64_t res = 0;

                        if (a <= c) {
                                b -= a, d -= c;
                                for (int i = a; i < c; i++) {
                                        b = max(b, L[i]);
                                        res += max(0, b - R[i]);
                                        b = min(b, R[i]);
                                }
                                b = max(b, d);
                                res += max(0, b - d);
                        } else {
                                b += a - 1, d += c - 1;
                                for (int i = a - 1; i >= c; i--) {
                                        b = max(b, L[i]);
                                        res += max(0, b - R[i]);
                                        b = min(b, R[i]);
                                }
                                b = max(b, d);
                                res += max(0, b - d);
                        }

                        cout << res << '\n';
                }
        }
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3098 ms 13236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 464 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 400 KB Output is correct
19 Correct 2 ms 516 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 472 KB Output is correct
28 Correct 1 ms 528 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 472 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 396 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 528 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Execution timed out 3098 ms 13236 KB Time limit exceeded
43 Halted 0 ms 0 KB -