oj.uz

Submission #1103890

# Submission time Handle Problem Language Result Execution time Memory
1103890 2024-10-22T06:23:42 Z Pacybwoah Escape Route 2 (JOI24_escape2) C++17
54 / 100
 3000 ms 73092 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
const int K = 1000;
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){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = 0;
            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";
                }
            }
            mini = min(mini, ans);
        }
        return mini;
    };
    auto pquery = [&](int pos, int kk){
        ll mini = inf;
        for(int times = 0; times < sz[pos]; times++){
            int id = pre[pos - 1] + times + 1;
            ll ans = 0;
            int k = kk;
            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;
    };
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << nquery(l, r - l) << "\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

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: variable 'pquery' set but not used [-Wunused-but-set-variable]
   92 |     auto pquery = [&](int pos, int kk){
      |          ^~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 60 ms 4452 KB Output is correct
3 Correct 53 ms 6228 KB Output is correct
4 Correct 74 ms 8128 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 127 ms 8264 KB Output is correct
7 Correct 79 ms 8268 KB Output is correct
8 Correct 93 ms 6096 KB Output is correct
9 Correct 81 ms 8244 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 60 ms 4452 KB Output is correct
3 Correct 53 ms 6228 KB Output is correct
4 Correct 74 ms 8128 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 127 ms 8264 KB Output is correct
7 Correct 79 ms 8268 KB Output is correct
8 Correct 93 ms 6096 KB Output is correct
9 Correct 81 ms 8244 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 95 ms 7164 KB Output is correct
12 Correct 89 ms 7240 KB Output is correct
13 Correct 82 ms 6988 KB Output is correct
14 Correct 94 ms 6984 KB Output is correct
15 Correct 99 ms 7496 KB Output is correct
16 Correct 45 ms 4428 KB Output is correct
17 Correct 108 ms 7892 KB Output is correct
18 Correct 90 ms 7496 KB Output is correct
19 Correct 79 ms 7756 KB Output is correct
20 Correct 100 ms 7148 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 60 ms 4452 KB Output is correct
3 Correct 53 ms 6228 KB Output is correct
4 Correct 74 ms 8128 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 127 ms 8264 KB Output is correct
7 Correct 79 ms 8268 KB Output is correct
8 Correct 93 ms 6096 KB Output is correct
9 Correct 81 ms 8244 KB Output is correct
10 Correct 254 ms 56876 KB Output is correct
11 Correct 482 ms 73092 KB Output is correct
12 Correct 444 ms 73004 KB Output is correct
13 Correct 360 ms 70956 KB Output is correct
14 Correct 453 ms 73004 KB Output is correct
15 Correct 482 ms 72928 KB Output is correct
16 Correct 238 ms 56872 KB Output is correct
17 Correct 345 ms 73072 KB Output is correct
18 Correct 170 ms 61128 KB Output is correct
19 Correct 166 ms 60604 KB Output is correct
20 Correct 176 ms 61000 KB Output is correct
21 Correct 165 ms 61128 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 60 ms 4452 KB Output is correct
3 Correct 53 ms 6228 KB Output is correct
4 Correct 74 ms 8128 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 127 ms 8264 KB Output is correct
7 Correct 79 ms 8268 KB Output is correct
8 Correct 93 ms 6096 KB Output is correct
9 Correct 81 ms 8244 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 95 ms 7164 KB Output is correct
12 Correct 89 ms 7240 KB Output is correct
13 Correct 82 ms 6988 KB Output is correct
14 Correct 94 ms 6984 KB Output is correct
15 Correct 99 ms 7496 KB Output is correct
16 Correct 45 ms 4428 KB Output is correct
17 Correct 108 ms 7892 KB Output is correct
18 Correct 90 ms 7496 KB Output is correct
19 Correct 79 ms 7756 KB Output is correct
20 Correct 100 ms 7148 KB Output is correct
21 Correct 254 ms 56876 KB Output is correct
22 Correct 482 ms 73092 KB Output is correct
23 Correct 444 ms 73004 KB Output is correct
24 Correct 360 ms 70956 KB Output is correct
25 Correct 453 ms 73004 KB Output is correct
26 Correct 482 ms 72928 KB Output is correct
27 Correct 238 ms 56872 KB Output is correct
28 Correct 345 ms 73072 KB Output is correct
29 Correct 170 ms 61128 KB Output is correct
30 Correct 166 ms 60604 KB Output is correct
31 Correct 176 ms 61000 KB Output is correct
32 Correct 165 ms 61128 KB Output is correct
33 Correct 410 ms 68400 KB Output is correct
34 Correct 377 ms 68080 KB Output is correct
35 Correct 371 ms 61960 KB Output is correct
36 Correct 346 ms 61896 KB Output is correct
37 Correct 307 ms 63176 KB Output is correct
38 Correct 216 ms 55432 KB Output is correct
39 Correct 364 ms 70700 KB Output is correct
40 Correct 317 ms 48680 KB Output is correct
41 Correct 281 ms 48664 KB Output is correct
42 Correct 371 ms 64476 KB Output is correct
43 Correct 299 ms 50440 KB Output is correct
44 Correct 366 ms 52472 KB Output is correct
45 Correct 174 ms 59080 KB Output is correct
46 Correct 158 ms 57544 KB Output is correct

Subtask #5
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 571 ms 55496 KB Output is correct
4 Correct 573 ms 55684 KB Output is correct
5 Correct 577 ms 55788 KB Output is correct
6 Correct 551 ms 55348 KB Output is correct
7 Correct 519 ms 55500 KB Output is correct
8 Correct 294 ms 30224 KB Output is correct
9 Correct 489 ms 55708 KB Output is correct
10 Execution timed out 3069 ms 28468 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 60 ms 4452 KB Output is correct
3 Correct 53 ms 6228 KB Output is correct
4 Correct 74 ms 8128 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 127 ms 8264 KB Output is correct
7 Correct 79 ms 8268 KB Output is correct
8 Correct 93 ms 6096 KB Output is correct
9 Correct 81 ms 8244 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 95 ms 7164 KB Output is correct
12 Correct 89 ms 7240 KB Output is correct
13 Correct 82 ms 6988 KB Output is correct
14 Correct 94 ms 6984 KB Output is correct
15 Correct 99 ms 7496 KB Output is correct
16 Correct 45 ms 4428 KB Output is correct
17 Correct 108 ms 7892 KB Output is correct
18 Correct 90 ms 7496 KB Output is correct
19 Correct 79 ms 7756 KB Output is correct
20 Correct 100 ms 7148 KB Output is correct
21 Correct 254 ms 56876 KB Output is correct
22 Correct 482 ms 73092 KB Output is correct
23 Correct 444 ms 73004 KB Output is correct
24 Correct 360 ms 70956 KB Output is correct
25 Correct 453 ms 73004 KB Output is correct
26 Correct 482 ms 72928 KB Output is correct
27 Correct 238 ms 56872 KB Output is correct
28 Correct 345 ms 73072 KB Output is correct
29 Correct 170 ms 61128 KB Output is correct
30 Correct 166 ms 60604 KB Output is correct
31 Correct 176 ms 61000 KB Output is correct
32 Correct 165 ms 61128 KB Output is correct
33 Correct 410 ms 68400 KB Output is correct
34 Correct 377 ms 68080 KB Output is correct
35 Correct 371 ms 61960 KB Output is correct
36 Correct 346 ms 61896 KB Output is correct
37 Correct 307 ms 63176 KB Output is correct
38 Correct 216 ms 55432 KB Output is correct
39 Correct 364 ms 70700 KB Output is correct
40 Correct 317 ms 48680 KB Output is correct
41 Correct 281 ms 48664 KB Output is correct
42 Correct 371 ms 64476 KB Output is correct
43 Correct 299 ms 50440 KB Output is correct
44 Correct 366 ms 52472 KB Output is correct
45 Correct 174 ms 59080 KB Output is correct
46 Correct 158 ms 57544 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 571 ms 55496 KB Output is correct
50 Correct 573 ms 55684 KB Output is correct
51 Correct 577 ms 55788 KB Output is correct
52 Correct 551 ms 55348 KB Output is correct
53 Correct 519 ms 55500 KB Output is correct
54 Correct 294 ms 30224 KB Output is correct
55 Correct 489 ms 55708 KB Output is correct
56 Execution timed out 3069 ms 28468 KB Time limit exceeded
57 Halted 0 ms 0 KB -