oj.uz

Submission #1010849

# Submission time Handle Problem Language Result Execution time Memory
1010849 2024-06-29T12:32:47 Z mdn2002 Overtaking (IOI23_overtaking) C++17
100 / 100
 3011 ms 1734316 KB 
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

long long offset, last_offset;

struct Node {
    long long valuel = -1, valuer = -1, lazy = -1;
    int left = -1, right = -1;
    Node() {}
    Node(long long l, long long r) {
        valuel = l, valuer = r;
    }
};
Node st[53000001];
int cnt = 0;

void update(long long x, long long y, long long val, int node, long long l, long long r) {
    long long left = st[node].valuel + last_offset;
    long long right = st[node].valuer + last_offset;

    if (right < x || y < left) return;

    long long mid = (l + r) / 2;
    if(st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = (Node(l, mid));
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = (Node(mid + 1, r));
    }
    if (st[node].lazy != -1) {
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (l != r) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
    }

    if (x <= left && right <= y) {
        st[node].lazy = val - offset;
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (l != r) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
        return;
    }
    update(x, y, val, st[node].left, l, mid);
    update(x, y, val, st[node].right, mid +1, r);
    st[node].valuel = st[st[node].left].valuel;
    st[node].valuer = st[st[node].right].valuer;
}

long long get(long long l, long long r, int node , long long left, long long right) {
    long long mid = (left + right) / 2;
    if(st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = (Node(left, mid));
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = (Node(mid + 1, right));
    }
    if (st[node].lazy != -1) {
        st[node].valuel = st[node].valuer = st[node].lazy;
        if (left != right) {
            int left = st[node].left, right = st[node].right;
            st[left].lazy = max(st[node].lazy, st[left].lazy);
            st[right].lazy = max(st[node].lazy, st[right].lazy);
        }
        st[node].lazy = -1;
    }

    if (l <= left && right <= r) return st[node].valuel;
    if (l <= mid) return get(l, r, st[node].left, left, mid);
    return get(l, r, st[node].right, mid + 1, right);
}

int l, n, x, m;
vector<int> s;
vector<pair<long long, int>> buses;
vector<vector<pair<long long, int>>> times;
vector<vector<pair<long long, long long>>> max_times;
long long arrival_time(long long time) {
    long long val = get(time, time, 0, 0, 1e18 + 1);
    return val + offset;
}

void init(int L, int N, std::vector <long long> T, std::vector <int> W, int X, int M, std::vector <int> S) {
    st[0] = (Node(0, 1e18));
    l = L, n = N, x = X, m = M, s = S;
    for (int i = 0; i < N; i ++) {
        if (W[i] < X) continue;
        buses.push_back({T[i], W[i]});
    }
    n = buses.size();
    times.push_back(buses);

    vector<pair<long long, long long>> bb;
    max_times.push_back(bb);
    for (int i = 1; i < m; i ++) {
        sort(times[i - 1].begin(), times[i - 1].end());
        long long max_time = 0, delta_time = S[i] - S[i - 1];
        vector<pair<long long, int>> a;
        vector<pair<long long, long long>> b;

        for (int j = 0; j < n; j ++) {
            long long past_time = times[i - 1][j].first, speed = times[i - 1][j].second;
            long long time = past_time + speed * delta_time;
            max_time = max(max_time, time);
            a.push_back({max_time, speed});
            b.push_back({past_time, max_time});
        }
        times.push_back(a);
        max_times.push_back(b);
    }

    for (int i = 1; i < m; i ++) {
        long long delta_time = S[i] - S[i - 1];
        offset += delta_time * x;
        for (int j = n - 1; j >= 0; j --) {
            long long time = max_times[i][j].second, left = max_times[i][j].first + 1, right = time - x * delta_time;
            update(left, right, time, 0, 0, 1e18 + 1);
        }
        last_offset += delta_time * x;
    }
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1659740 KB Output is correct

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1659720 KB Output is correct
2 Correct 567 ms 1659704 KB Output is correct
3 Correct 558 ms 1659788 KB Output is correct
4 Correct 551 ms 1659728 KB Output is correct
5 Correct 555 ms 1659728 KB Output is correct
6 Correct 575 ms 1660116 KB Output is correct
7 Correct 593 ms 1659888 KB Output is correct
8 Correct 567 ms 1659908 KB Output is correct
9 Correct 520 ms 1659936 KB Output is correct
10 Correct 528 ms 1659984 KB Output is correct
11 Correct 541 ms 1659988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 1659676 KB Output is correct
2 Correct 554 ms 1659720 KB Output is correct
3 Correct 528 ms 1659988 KB Output is correct
4 Correct 552 ms 1659728 KB Output is correct
5 Correct 590 ms 1659752 KB Output is correct
6 Correct 568 ms 1659984 KB Output is correct
7 Correct 567 ms 1659896 KB Output is correct
8 Correct 564 ms 1659984 KB Output is correct
9 Correct 565 ms 1659924 KB Output is correct
10 Correct 561 ms 1659892 KB Output is correct
11 Correct 579 ms 1659988 KB Output is correct
12 Correct 561 ms 1659984 KB Output is correct
13 Correct 510 ms 1659732 KB Output is correct
14 Correct 501 ms 1659860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1659740 KB Output is correct
2 Correct 653 ms 1659720 KB Output is correct
3 Correct 567 ms 1659704 KB Output is correct
4 Correct 558 ms 1659788 KB Output is correct
5 Correct 551 ms 1659728 KB Output is correct
6 Correct 536 ms 1659676 KB Output is correct
7 Correct 554 ms 1659720 KB Output is correct
8 Correct 528 ms 1659988 KB Output is correct
9 Correct 556 ms 1660092 KB Output is correct
10 Correct 551 ms 1660180 KB Output is correct
11 Correct 565 ms 1660240 KB Output is correct
12 Correct 545 ms 1660240 KB Output is correct
13 Correct 572 ms 1660060 KB Output is correct
14 Correct 540 ms 1660128 KB Output is correct
15 Correct 538 ms 1660240 KB Output is correct
16 Correct 553 ms 1660408 KB Output is correct
17 Correct 549 ms 1660240 KB Output is correct
18 Correct 552 ms 1660244 KB Output is correct
19 Correct 553 ms 1660124 KB Output is correct
20 Correct 546 ms 1660244 KB Output is correct
21 Correct 519 ms 1659988 KB Output is correct
22 Correct 552 ms 1660020 KB Output is correct
23 Correct 534 ms 1660244 KB Output is correct
24 Correct 538 ms 1660136 KB Output is correct
25 Correct 531 ms 1659988 KB Output is correct
26 Correct 567 ms 1660148 KB Output is correct
27 Correct 568 ms 1660148 KB Output is correct
28 Correct 588 ms 1660092 KB Output is correct
29 Correct 572 ms 1659948 KB Output is correct
30 Correct 548 ms 1659988 KB Output is correct
31 Correct 559 ms 1660016 KB Output is correct
32 Correct 582 ms 1660088 KB Output is correct
33 Correct 604 ms 1660152 KB Output is correct
34 Correct 574 ms 1660212 KB Output is correct
35 Correct 574 ms 1660020 KB Output is correct
36 Correct 540 ms 1660152 KB Output is correct
37 Correct 564 ms 1660084 KB Output is correct
38 Correct 583 ms 1659880 KB Output is correct
39 Correct 564 ms 1659768 KB Output is correct
40 Correct 563 ms 1660156 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1659740 KB Output is correct
2 Correct 653 ms 1659720 KB Output is correct
3 Correct 567 ms 1659704 KB Output is correct
4 Correct 558 ms 1659788 KB Output is correct
5 Correct 551 ms 1659728 KB Output is correct
6 Correct 555 ms 1659728 KB Output is correct
7 Correct 575 ms 1660116 KB Output is correct
8 Correct 593 ms 1659888 KB Output is correct
9 Correct 567 ms 1659908 KB Output is correct
10 Correct 520 ms 1659936 KB Output is correct
11 Correct 528 ms 1659984 KB Output is correct
12 Correct 541 ms 1659988 KB Output is correct
13 Correct 536 ms 1659676 KB Output is correct
14 Correct 554 ms 1659720 KB Output is correct
15 Correct 528 ms 1659988 KB Output is correct
16 Correct 556 ms 1660092 KB Output is correct
17 Correct 551 ms 1660180 KB Output is correct
18 Correct 565 ms 1660240 KB Output is correct
19 Correct 545 ms 1660240 KB Output is correct
20 Correct 572 ms 1660060 KB Output is correct
21 Correct 540 ms 1660128 KB Output is correct
22 Correct 538 ms 1660240 KB Output is correct
23 Correct 553 ms 1660408 KB Output is correct
24 Correct 549 ms 1660240 KB Output is correct
25 Correct 552 ms 1660244 KB Output is correct
26 Correct 553 ms 1660124 KB Output is correct
27 Correct 546 ms 1660244 KB Output is correct
28 Correct 519 ms 1659988 KB Output is correct
29 Correct 552 ms 1660020 KB Output is correct
30 Correct 534 ms 1660244 KB Output is correct
31 Correct 538 ms 1660136 KB Output is correct
32 Correct 531 ms 1659988 KB Output is correct
33 Correct 567 ms 1660148 KB Output is correct
34 Correct 568 ms 1660148 KB Output is correct
35 Correct 588 ms 1660092 KB Output is correct
36 Correct 572 ms 1659948 KB Output is correct
37 Correct 548 ms 1659988 KB Output is correct
38 Correct 559 ms 1660016 KB Output is correct
39 Correct 582 ms 1660088 KB Output is correct
40 Correct 604 ms 1660152 KB Output is correct
41 Correct 574 ms 1660212 KB Output is correct
42 Correct 574 ms 1660020 KB Output is correct
43 Correct 540 ms 1660152 KB Output is correct
44 Correct 564 ms 1660084 KB Output is correct
45 Correct 583 ms 1659880 KB Output is correct
46 Correct 564 ms 1659768 KB Output is correct
47 Correct 563 ms 1660156 KB Output is correct
48 Correct 1274 ms 1691268 KB Output is correct
49 Correct 1341 ms 1691520 KB Output is correct
50 Correct 1413 ms 1691520 KB Output is correct
51 Correct 1326 ms 1691592 KB Output is correct
52 Correct 1346 ms 1691520 KB Output is correct
53 Correct 1336 ms 1691376 KB Output is correct
54 Correct 1312 ms 1691524 KB Output is correct
55 Correct 1121 ms 1691416 KB Output is correct
56 Correct 1585 ms 1691524 KB Output is correct
57 Correct 1295 ms 1691528 KB Output is correct
58 Correct 1329 ms 1691524 KB Output is correct
59 Correct 1338 ms 1691360 KB Output is correct
60 Correct 1361 ms 1691564 KB Output is correct
61 Correct 1392 ms 1691524 KB Output is correct
62 Correct 575 ms 1660148 KB Output is correct
63 Correct 568 ms 1660116 KB Output is correct
64 Correct 958 ms 1675860 KB Output is correct
65 Correct 989 ms 1675752 KB Output is correct
66 Correct 1756 ms 1691552 KB Output is correct
67 Correct 1336 ms 1691732 KB Output is correct
68 Correct 1390 ms 1691456 KB Output is correct
69 Correct 1431 ms 1691524 KB Output is correct
70 Correct 1494 ms 1691524 KB Output is correct
71 Correct 1587 ms 1691732 KB Output is correct
72 Correct 1775 ms 1691524 KB Output is correct
73 Correct 1551 ms 1691524 KB Output is correct
74 Correct 1600 ms 1691476 KB Output is correct
75 Correct 564 ms 1659988 KB Output is correct
76 Correct 557 ms 1660032 KB Output is correct
77 Correct 525 ms 1660020 KB Output is correct
78 Correct 1330 ms 1691496 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 1659740 KB Output is correct
2 Correct 653 ms 1659720 KB Output is correct
3 Correct 567 ms 1659704 KB Output is correct
4 Correct 558 ms 1659788 KB Output is correct
5 Correct 551 ms 1659728 KB Output is correct
6 Correct 555 ms 1659728 KB Output is correct
7 Correct 575 ms 1660116 KB Output is correct
8 Correct 593 ms 1659888 KB Output is correct
9 Correct 567 ms 1659908 KB Output is correct
10 Correct 520 ms 1659936 KB Output is correct
11 Correct 528 ms 1659984 KB Output is correct
12 Correct 541 ms 1659988 KB Output is correct
13 Correct 536 ms 1659676 KB Output is correct
14 Correct 554 ms 1659720 KB Output is correct
15 Correct 528 ms 1659988 KB Output is correct
16 Correct 552 ms 1659728 KB Output is correct
17 Correct 590 ms 1659752 KB Output is correct
18 Correct 568 ms 1659984 KB Output is correct
19 Correct 567 ms 1659896 KB Output is correct
20 Correct 564 ms 1659984 KB Output is correct
21 Correct 565 ms 1659924 KB Output is correct
22 Correct 561 ms 1659892 KB Output is correct
23 Correct 579 ms 1659988 KB Output is correct
24 Correct 561 ms 1659984 KB Output is correct
25 Correct 510 ms 1659732 KB Output is correct
26 Correct 501 ms 1659860 KB Output is correct
27 Correct 556 ms 1660092 KB Output is correct
28 Correct 551 ms 1660180 KB Output is correct
29 Correct 565 ms 1660240 KB Output is correct
30 Correct 545 ms 1660240 KB Output is correct
31 Correct 572 ms 1660060 KB Output is correct
32 Correct 540 ms 1660128 KB Output is correct
33 Correct 538 ms 1660240 KB Output is correct
34 Correct 553 ms 1660408 KB Output is correct
35 Correct 549 ms 1660240 KB Output is correct
36 Correct 552 ms 1660244 KB Output is correct
37 Correct 553 ms 1660124 KB Output is correct
38 Correct 546 ms 1660244 KB Output is correct
39 Correct 519 ms 1659988 KB Output is correct
40 Correct 552 ms 1660020 KB Output is correct
41 Correct 534 ms 1660244 KB Output is correct
42 Correct 538 ms 1660136 KB Output is correct
43 Correct 531 ms 1659988 KB Output is correct
44 Correct 567 ms 1660148 KB Output is correct
45 Correct 568 ms 1660148 KB Output is correct
46 Correct 588 ms 1660092 KB Output is correct
47 Correct 572 ms 1659948 KB Output is correct
48 Correct 548 ms 1659988 KB Output is correct
49 Correct 559 ms 1660016 KB Output is correct
50 Correct 582 ms 1660088 KB Output is correct
51 Correct 604 ms 1660152 KB Output is correct
52 Correct 574 ms 1660212 KB Output is correct
53 Correct 574 ms 1660020 KB Output is correct
54 Correct 540 ms 1660152 KB Output is correct
55 Correct 564 ms 1660084 KB Output is correct
56 Correct 583 ms 1659880 KB Output is correct
57 Correct 564 ms 1659768 KB Output is correct
58 Correct 563 ms 1660156 KB Output is correct
59 Correct 1274 ms 1691268 KB Output is correct
60 Correct 1341 ms 1691520 KB Output is correct
61 Correct 1413 ms 1691520 KB Output is correct
62 Correct 1326 ms 1691592 KB Output is correct
63 Correct 1346 ms 1691520 KB Output is correct
64 Correct 1336 ms 1691376 KB Output is correct
65 Correct 1312 ms 1691524 KB Output is correct
66 Correct 1121 ms 1691416 KB Output is correct
67 Correct 1585 ms 1691524 KB Output is correct
68 Correct 1295 ms 1691528 KB Output is correct
69 Correct 1329 ms 1691524 KB Output is correct
70 Correct 1338 ms 1691360 KB Output is correct
71 Correct 1361 ms 1691564 KB Output is correct
72 Correct 1392 ms 1691524 KB Output is correct
73 Correct 575 ms 1660148 KB Output is correct
74 Correct 568 ms 1660116 KB Output is correct
75 Correct 958 ms 1675860 KB Output is correct
76 Correct 989 ms 1675752 KB Output is correct
77 Correct 1756 ms 1691552 KB Output is correct
78 Correct 1336 ms 1691732 KB Output is correct
79 Correct 1390 ms 1691456 KB Output is correct
80 Correct 1431 ms 1691524 KB Output is correct
81 Correct 1494 ms 1691524 KB Output is correct
82 Correct 1587 ms 1691732 KB Output is correct
83 Correct 1775 ms 1691524 KB Output is correct
84 Correct 1551 ms 1691524 KB Output is correct
85 Correct 1600 ms 1691476 KB Output is correct
86 Correct 564 ms 1659988 KB Output is correct
87 Correct 557 ms 1660032 KB Output is correct
88 Correct 525 ms 1660020 KB Output is correct
89 Correct 1330 ms 1691496 KB Output is correct
90 Correct 1336 ms 1694560 KB Output is correct
91 Correct 2226 ms 1726288 KB Output is correct
92 Correct 1976 ms 1725856 KB Output is correct
93 Correct 1912 ms 1726288 KB Output is correct
94 Correct 1852 ms 1725884 KB Output is correct
95 Correct 1881 ms 1726208 KB Output is correct
96 Correct 1839 ms 1726508 KB Output is correct
97 Correct 1238 ms 1694696 KB Output is correct
98 Correct 1794 ms 1725988 KB Output is correct
99 Correct 1977 ms 1727176 KB Output is correct
100 Correct 1863 ms 1726464 KB Output is correct
101 Correct 1794 ms 1726112 KB Output is correct
102 Correct 1741 ms 1726032 KB Output is correct
103 Correct 1830 ms 1726264 KB Output is correct
104 Correct 1384 ms 1708740 KB Output is correct
105 Correct 1526 ms 1713100 KB Output is correct
106 Correct 2420 ms 1734316 KB Output is correct
107 Correct 1910 ms 1734032 KB Output is correct
108 Correct 2013 ms 1734212 KB Output is correct
109 Correct 2050 ms 1734156 KB Output is correct
110 Correct 2109 ms 1734212 KB Output is correct
111 Correct 2301 ms 1726548 KB Output is correct
112 Correct 2265 ms 1726472 KB Output is correct
113 Correct 2563 ms 1727648 KB Output is correct
114 Correct 2851 ms 1728824 KB Output is correct
115 Correct 2516 ms 1726796 KB Output is correct
116 Correct 2572 ms 1727568 KB Output is correct
117 Correct 1213 ms 1698924 KB Output is correct
118 Correct 1151 ms 1698972 KB Output is correct
119 Correct 1160 ms 1697056 KB Output is correct
120 Correct 1245 ms 1699116 KB Output is correct
121 Correct 1222 ms 1700152 KB Output is correct
122 Correct 1991 ms 1720588 KB Output is correct
123 Correct 2834 ms 1728592 KB Output is correct
124 Correct 2986 ms 1728592 KB Output is correct
125 Correct 3011 ms 1728652 KB Output is correct