oj.uz

Submission #1103928

# Submission time Handle Problem Language Result Execution time Memory
1103928 2024-10-22T09:24:21 Z Pacybwoah Escape Route 2 (JOI24_escape2) C++17
100 / 100
 819 ms 88792 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
const int K = 1500;
using namespace std;
typedef long long ll;
const ll inf = 8e18;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m = 0;
    ll t;
    cin >> n >> t;
    vector<vector<pair<int, int>>> rngs(n);
    vector<int> sz(n), pre(n);
    for(int i = 1; i < n; i++){
        int tmp;
        cin >> tmp;
        for(int j = 0; j < tmp; j++){
            int a, b;
            cin >> a >> b;
            rngs[i].emplace_back(a, b);
        }
        sort(rngs[i].begin(), rngs[i].end());
        vector<pair<int, int>> vtmp;
        int mini = 2e9;
        for(int j = tmp - 1; j >= 0; j--){
            auto x = rngs[i][j];
            if(x.second < mini){
                mini = x.second;
                vtmp.push_back(x);
            }
        }
        reverse(vtmp.begin(), vtmp.end());
        rngs[i] = vtmp;
        sz[i] = (int)rngs[i].size();
        m += sz[i];
        pre[i] = pre[i - 1] + sz[i];
    }
    vector<vector<pair<int, ll>>> panc(17, vector<pair<int, ll>>(m + 1)), nanc(17, vector<pair<int, ll>>(m + 1));
    vector<pair<int, ll>> lst(m + 1), nxt(m + 1);
    for(int i = 2; i < n; i++){
        int ptr = 0;
        for(int j = 0; j < sz[i - 1]; j++){
            int id = pre[i - 2] + j + 1;
            while(ptr < sz[i] && rngs[i][ptr].first < rngs[i - 1][j].second) ptr++;
            if(ptr < sz[i]) nxt[id] = make_pair(pre[i - 1] + ptr + 1, rngs[i][ptr].first - rngs[i - 1][j].second);
            else nxt[id] = make_pair(pre[i - 1] + 1, t + rngs[i][0].first - rngs[i - 1][j].second);
        }
        ptr = -1;
        for(int j = 0; j < sz[i]; j++){
            int id = pre[i - 1] + j + 1;
            while(ptr < sz[i - 1] - 1 && rngs[i - 1][ptr + 1].second <= rngs[i][j].first) ptr++;
            if(ptr >= 0) lst[id] = make_pair(pre[i - 2] + ptr + 1, rngs[i][j].first - rngs[i - 1][ptr].second);
            else lst[id] = make_pair(pre[i - 1], t + rngs[i][j].first - rngs[i - 1][sz[i - 1] - 1].second);
        }
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < sz[i]; j++){
            int id = pre[i - 1] + j + 1;
            nanc[0][id] = make_pair(id, rngs[i][j].second - rngs[i][j].first);
            panc[0][id] = nanc[0][id];
        }
    }
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= m; j++){
            nanc[i][j] = make_pair(nanc[i - 1][nxt[nanc[i - 1][j].first].first].first, nanc[i - 1][j].second + nanc[i - 1][nxt[nanc[i - 1][j].first].first].second + nxt[nanc[i - 1][j].first].second);
            panc[i][j] = make_pair(panc[i - 1][lst[panc[i - 1][j].first].first].first, panc[i - 1][j].second + panc[i - 1][lst[panc[i - 1][j].first].first].second + lst[panc[i - 1][j].first].second);
        }
    }
    auto nquery = [&](int pos, int kk, int k2){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = -rngs[pos][times].second + rngs[pos][times].first;
            int k = kk;
            for(int i = 0; i < 17; i++){
                if(k & (1 << i)){
                    k -= (1 << i);
                    ans += nanc[i][id].second;
                    id = nanc[i][id].first;
                    if(k > 0) ans += nxt[id].second;
                    id = nxt[id].first;
                    //cout << id << " " << ans << "\n";
                }
            }
            //cout << ans << "\n";
            id = pre[pos - 1] + times + 1;
            k = k2;
            for(int i = 0; i < 17; i++){
                if(k & (1 << i)){
                    k -= (1 << i);
                    ans += panc[i][id].second;
                    id = panc[i][id].first;
                    if(k > 0) ans += lst[id].second;
                    id = lst[id].first;
                }
            }
            mini = min(mini, ans);
        }
        return mini;
    };
    vector<vector<pair<int, int>>> st(17, vector<pair<int, int>>(n));
    for(int j = 1; j < n; j++){
        st[0][j] = make_pair(sz[j], j);
    }
    for(int i = 1; i < 17; i++) for(int j = 1; j < n; j++) st[i][j] = min(st[i - 1][j], st[i - 1][min(n - 1, j + (1 << (i - 1)))]);
    vector<int> bases(n);
    for(int i = 1; i < n; i++){
        bases[i] = bases[i - 1];
        if(i == (1 << (bases[i] + 1))) bases[i]++;
    }
    auto query = [&](int l, int r){
        r--;
        int len = r - l + 1;
        return min(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]).second;
    };
    int q;
    cin >> q;
    vector<ll> anss(q);
    vector<vector<pair<int, int>>> queries(n + 1);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        if(r - l > K){
            int best = query(l, r);
            anss[i] = nquery(best, r - best, best - l + 1);
            //cout << best << "\n";
        }
        else{
            queries[l].emplace_back(r, i);
        }
    }
    ll mini = inf;
    for(int i = 1; i < n; i++){
        if(queries[i].empty()) continue;
        sort(queries[i].begin(), queries[i].end());
        int szz = queries[i].size();
        int ptr = 0;
        vector<ll> ans(sz[i]);
        vector<int> id(sz[i]);
        for(int j = 0; j < sz[i]; j++) id[j] = pre[i - 1] + j + 1;
        for(int j = i; j < min(n, i + K); j++){
            mini = inf;
            for(int k = 0; k < sz[i]; k++){
                ans[k] += nanc[0][id[k]].second;
                mini = min(mini, ans[k]);
            }
            while(ptr < szz && queries[i][ptr].first - 1 == j){
                anss[queries[i][ptr].second] = mini;
                ptr++;
            }
            for(int k = 0; k < sz[i]; k++){
                ans[k] += nxt[id[k]].second;
                id[k] = nxt[id[k]].first;
            }
        }
    }
    for(int i = 0; i < q; i++) cout << anss[i] << "\n";
    //for(int i = 1; i <= m; i++) cout << nanc[1][i].first << " " << nanc[1][i].second << '\n';
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run escape.cpp

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 9896 KB Output is correct
3 Correct 54 ms 10692 KB Output is correct
4 Correct 77 ms 11848 KB Output is correct
5 Correct 65 ms 10056 KB Output is correct
6 Correct 75 ms 12104 KB Output is correct
7 Correct 82 ms 12872 KB Output is correct
8 Correct 55 ms 10284 KB Output is correct
9 Correct 74 ms 11592 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 9896 KB Output is correct
3 Correct 54 ms 10692 KB Output is correct
4 Correct 77 ms 11848 KB Output is correct
5 Correct 65 ms 10056 KB Output is correct
6 Correct 75 ms 12104 KB Output is correct
7 Correct 82 ms 12872 KB Output is correct
8 Correct 55 ms 10284 KB Output is correct
9 Correct 74 ms 11592 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 70 ms 13124 KB Output is correct
12 Correct 78 ms 11080 KB Output is correct
13 Correct 70 ms 10824 KB Output is correct
14 Correct 69 ms 11596 KB Output is correct
15 Correct 74 ms 11336 KB Output is correct
16 Correct 64 ms 9860 KB Output is correct
17 Correct 71 ms 11936 KB Output is correct
18 Correct 74 ms 11592 KB Output is correct
19 Correct 78 ms 11856 KB Output is correct
20 Correct 75 ms 11080 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 9896 KB Output is correct
3 Correct 54 ms 10692 KB Output is correct
4 Correct 77 ms 11848 KB Output is correct
5 Correct 65 ms 10056 KB Output is correct
6 Correct 75 ms 12104 KB Output is correct
7 Correct 82 ms 12872 KB Output is correct
8 Correct 55 ms 10284 KB Output is correct
9 Correct 74 ms 11592 KB Output is correct
10 Correct 275 ms 69084 KB Output is correct
11 Correct 471 ms 86316 KB Output is correct
12 Correct 496 ms 88644 KB Output is correct
13 Correct 434 ms 86828 KB Output is correct
14 Correct 534 ms 87152 KB Output is correct
15 Correct 442 ms 86316 KB Output is correct
16 Correct 323 ms 69492 KB Output is correct
17 Correct 439 ms 88792 KB Output is correct
18 Correct 161 ms 73928 KB Output is correct
19 Correct 169 ms 73728 KB Output is correct
20 Correct 188 ms 73960 KB Output is correct
21 Correct 180 ms 73988 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 9896 KB Output is correct
3 Correct 54 ms 10692 KB Output is correct
4 Correct 77 ms 11848 KB Output is correct
5 Correct 65 ms 10056 KB Output is correct
6 Correct 75 ms 12104 KB Output is correct
7 Correct 82 ms 12872 KB Output is correct
8 Correct 55 ms 10284 KB Output is correct
9 Correct 74 ms 11592 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 70 ms 13124 KB Output is correct
12 Correct 78 ms 11080 KB Output is correct
13 Correct 70 ms 10824 KB Output is correct
14 Correct 69 ms 11596 KB Output is correct
15 Correct 74 ms 11336 KB Output is correct
16 Correct 64 ms 9860 KB Output is correct
17 Correct 71 ms 11936 KB Output is correct
18 Correct 74 ms 11592 KB Output is correct
19 Correct 78 ms 11856 KB Output is correct
20 Correct 75 ms 11080 KB Output is correct
21 Correct 275 ms 69084 KB Output is correct
22 Correct 471 ms 86316 KB Output is correct
23 Correct 496 ms 88644 KB Output is correct
24 Correct 434 ms 86828 KB Output is correct
25 Correct 534 ms 87152 KB Output is correct
26 Correct 442 ms 86316 KB Output is correct
27 Correct 323 ms 69492 KB Output is correct
28 Correct 439 ms 88792 KB Output is correct
29 Correct 161 ms 73928 KB Output is correct
30 Correct 169 ms 73728 KB Output is correct
31 Correct 188 ms 73960 KB Output is correct
32 Correct 180 ms 73988 KB Output is correct
33 Correct 819 ms 71980 KB Output is correct
34 Correct 811 ms 74248 KB Output is correct
35 Correct 777 ms 64712 KB Output is correct
36 Correct 729 ms 66504 KB Output is correct
37 Correct 634 ms 65680 KB Output is correct
38 Correct 351 ms 63212 KB Output is correct
39 Correct 436 ms 81640 KB Output is correct
40 Correct 455 ms 50728 KB Output is correct
41 Correct 438 ms 57156 KB Output is correct
42 Correct 532 ms 74200 KB Output is correct
43 Correct 368 ms 53256 KB Output is correct
44 Correct 449 ms 55288 KB Output is correct
45 Correct 169 ms 66760 KB Output is correct
46 Correct 182 ms 62656 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 106 ms 55148 KB Output is correct
4 Correct 99 ms 57484 KB Output is correct
5 Correct 106 ms 55224 KB Output is correct
6 Correct 97 ms 55012 KB Output is correct
7 Correct 103 ms 56536 KB Output is correct
8 Correct 92 ms 30088 KB Output is correct
9 Correct 109 ms 55516 KB Output is correct
10 Correct 57 ms 30240 KB Output is correct
11 Correct 210 ms 75464 KB Output is correct
12 Correct 197 ms 66772 KB Output is correct
13 Correct 228 ms 60360 KB Output is correct
14 Correct 187 ms 60456 KB Output is correct
15 Correct 242 ms 58240 KB Output is correct
16 Correct 182 ms 58312 KB Output is correct
17 Correct 215 ms 59592 KB Output is correct
18 Correct 217 ms 55172 KB Output is correct
19 Correct 132 ms 54984 KB Output is correct
20 Correct 104 ms 70472 KB Output is correct
21 Correct 139 ms 68248 KB Output is correct
22 Correct 97 ms 62664 KB Output is correct
23 Correct 159 ms 62664 KB Output is correct
24 Correct 183 ms 64024 KB Output is correct
25 Correct 104 ms 62568 KB Output is correct
26 Correct 198 ms 63688 KB Output is correct
27 Correct 208 ms 75976 KB Output is correct
28 Correct 189 ms 75452 KB Output is correct
29 Correct 227 ms 75368 KB Output is correct
30 Correct 110 ms 13148 KB Output is correct
31 Correct 42 ms 5892 KB Output is correct
32 Correct 107 ms 18424 KB Output is correct
33 Correct 41 ms 6848 KB Output is correct
34 Correct 50 ms 12460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 51 ms 9896 KB Output is correct
3 Correct 54 ms 10692 KB Output is correct
4 Correct 77 ms 11848 KB Output is correct
5 Correct 65 ms 10056 KB Output is correct
6 Correct 75 ms 12104 KB Output is correct
7 Correct 82 ms 12872 KB Output is correct
8 Correct 55 ms 10284 KB Output is correct
9 Correct 74 ms 11592 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 70 ms 13124 KB Output is correct
12 Correct 78 ms 11080 KB Output is correct
13 Correct 70 ms 10824 KB Output is correct
14 Correct 69 ms 11596 KB Output is correct
15 Correct 74 ms 11336 KB Output is correct
16 Correct 64 ms 9860 KB Output is correct
17 Correct 71 ms 11936 KB Output is correct
18 Correct 74 ms 11592 KB Output is correct
19 Correct 78 ms 11856 KB Output is correct
20 Correct 75 ms 11080 KB Output is correct
21 Correct 275 ms 69084 KB Output is correct
22 Correct 471 ms 86316 KB Output is correct
23 Correct 496 ms 88644 KB Output is correct
24 Correct 434 ms 86828 KB Output is correct
25 Correct 534 ms 87152 KB Output is correct
26 Correct 442 ms 86316 KB Output is correct
27 Correct 323 ms 69492 KB Output is correct
28 Correct 439 ms 88792 KB Output is correct
29 Correct 161 ms 73928 KB Output is correct
30 Correct 169 ms 73728 KB Output is correct
31 Correct 188 ms 73960 KB Output is correct
32 Correct 180 ms 73988 KB Output is correct
33 Correct 819 ms 71980 KB Output is correct
34 Correct 811 ms 74248 KB Output is correct
35 Correct 777 ms 64712 KB Output is correct
36 Correct 729 ms 66504 KB Output is correct
37 Correct 634 ms 65680 KB Output is correct
38 Correct 351 ms 63212 KB Output is correct
39 Correct 436 ms 81640 KB Output is correct
40 Correct 455 ms 50728 KB Output is correct
41 Correct 438 ms 57156 KB Output is correct
42 Correct 532 ms 74200 KB Output is correct
43 Correct 368 ms 53256 KB Output is correct
44 Correct 449 ms 55288 KB Output is correct
45 Correct 169 ms 66760 KB Output is correct
46 Correct 182 ms 62656 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 106 ms 55148 KB Output is correct
50 Correct 99 ms 57484 KB Output is correct
51 Correct 106 ms 55224 KB Output is correct
52 Correct 97 ms 55012 KB Output is correct
53 Correct 103 ms 56536 KB Output is correct
54 Correct 92 ms 30088 KB Output is correct
55 Correct 109 ms 55516 KB Output is correct
56 Correct 57 ms 30240 KB Output is correct
57 Correct 210 ms 75464 KB Output is correct
58 Correct 197 ms 66772 KB Output is correct
59 Correct 228 ms 60360 KB Output is correct
60 Correct 187 ms 60456 KB Output is correct
61 Correct 242 ms 58240 KB Output is correct
62 Correct 182 ms 58312 KB Output is correct
63 Correct 215 ms 59592 KB Output is correct
64 Correct 217 ms 55172 KB Output is correct
65 Correct 132 ms 54984 KB Output is correct
66 Correct 104 ms 70472 KB Output is correct
67 Correct 139 ms 68248 KB Output is correct
68 Correct 97 ms 62664 KB Output is correct
69 Correct 159 ms 62664 KB Output is correct
70 Correct 183 ms 64024 KB Output is correct
71 Correct 104 ms 62568 KB Output is correct
72 Correct 198 ms 63688 KB Output is correct
73 Correct 208 ms 75976 KB Output is correct
74 Correct 189 ms 75452 KB Output is correct
75 Correct 227 ms 75368 KB Output is correct
76 Correct 110 ms 13148 KB Output is correct
77 Correct 42 ms 5892 KB Output is correct
78 Correct 107 ms 18424 KB Output is correct
79 Correct 41 ms 6848 KB Output is correct
80 Correct 50 ms 12460 KB Output is correct
81 Correct 195 ms 69048 KB Output is correct
82 Correct 191 ms 69100 KB Output is correct
83 Correct 179 ms 69172 KB Output is correct
84 Correct 183 ms 68916 KB Output is correct
85 Correct 208 ms 68920 KB Output is correct
86 Correct 133 ms 38988 KB Output is correct
87 Correct 170 ms 69936 KB Output is correct
88 Correct 200 ms 67960 KB Output is correct
89 Correct 204 ms 71980 KB Output is correct
90 Correct 149 ms 39992 KB Output is correct
91 Correct 95 ms 41904 KB Output is correct
92 Correct 353 ms 74728 KB Output is correct
93 Correct 447 ms 72424 KB Output is correct
94 Correct 393 ms 69404 KB Output is correct
95 Correct 511 ms 72236 KB Output is correct
96 Correct 338 ms 71352 KB Output is correct
97 Correct 203 ms 69728 KB Output is correct
98 Correct 170 ms 81284 KB Output is correct
99 Correct 336 ms 78780 KB Output is correct
100 Correct 174 ms 74028 KB Output is correct
101 Correct 356 ms 74560 KB Output is correct
102 Correct 375 ms 75784 KB Output is correct
103 Correct 207 ms 74256 KB Output is correct
104 Correct 382 ms 74284 KB Output is correct
105 Correct 113 ms 18244 KB Output is correct
106 Correct 90 ms 13760 KB Output is correct
107 Correct 180 ms 25328 KB Output is correct
108 Correct 97 ms 14956 KB Output is correct
109 Correct 118 ms 19848 KB Output is correct