oj.uz

Submission #1103896

# Submission time Handle Problem Language Result Execution time Memory
1103896 2024-10-22T06:45:49 Z Pacybwoah Escape Route 2 (JOI24_escape2) C++17
54 / 100
 3000 ms 89360 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
const int K = 1;
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);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        if(r - l >= K){
            int best = query(l, r);
            cout << nquery(best, r - best, best - l + 1) << "\n"; 
            //cout << best << "\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 50 ms 5724 KB Output is correct
3 Correct 64 ms 8272 KB Output is correct
4 Correct 84 ms 10320 KB Output is correct
5 Correct 77 ms 8604 KB Output is correct
6 Correct 88 ms 10432 KB Output is correct
7 Correct 88 ms 10572 KB Output is correct
8 Correct 67 ms 8100 KB Output is correct
9 Correct 96 ms 10312 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 50 ms 5724 KB Output is correct
3 Correct 64 ms 8272 KB Output is correct
4 Correct 84 ms 10320 KB Output is correct
5 Correct 77 ms 8604 KB Output is correct
6 Correct 88 ms 10432 KB Output is correct
7 Correct 88 ms 10572 KB Output is correct
8 Correct 67 ms 8100 KB Output is correct
9 Correct 96 ms 10312 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 127 ms 9424 KB Output is correct
12 Correct 121 ms 9552 KB Output is correct
13 Correct 117 ms 9544 KB Output is correct
14 Correct 126 ms 9288 KB Output is correct
15 Correct 86 ms 9800 KB Output is correct
16 Correct 60 ms 6984 KB Output is correct
17 Correct 84 ms 10312 KB Output is correct
18 Correct 80 ms 9720 KB Output is correct
19 Correct 89 ms 10312 KB Output is correct
20 Correct 79 ms 9804 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 50 ms 5724 KB Output is correct
3 Correct 64 ms 8272 KB Output is correct
4 Correct 84 ms 10320 KB Output is correct
5 Correct 77 ms 8604 KB Output is correct
6 Correct 88 ms 10432 KB Output is correct
7 Correct 88 ms 10572 KB Output is correct
8 Correct 67 ms 8100 KB Output is correct
9 Correct 96 ms 10312 KB Output is correct
10 Correct 330 ms 68044 KB Output is correct
11 Correct 464 ms 89360 KB Output is correct
12 Correct 390 ms 87184 KB Output is correct
13 Correct 398 ms 84780 KB Output is correct
14 Correct 608 ms 86828 KB Output is correct
15 Correct 500 ms 88372 KB Output is correct
16 Correct 256 ms 67956 KB Output is correct
17 Correct 491 ms 88364 KB Output is correct
18 Correct 220 ms 73164 KB Output is correct
19 Correct 183 ms 72648 KB Output is correct
20 Correct 208 ms 74440 KB Output is correct
21 Correct 190 ms 74064 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 50 ms 5724 KB Output is correct
3 Correct 64 ms 8272 KB Output is correct
4 Correct 84 ms 10320 KB Output is correct
5 Correct 77 ms 8604 KB Output is correct
6 Correct 88 ms 10432 KB Output is correct
7 Correct 88 ms 10572 KB Output is correct
8 Correct 67 ms 8100 KB Output is correct
9 Correct 96 ms 10312 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 127 ms 9424 KB Output is correct
12 Correct 121 ms 9552 KB Output is correct
13 Correct 117 ms 9544 KB Output is correct
14 Correct 126 ms 9288 KB Output is correct
15 Correct 86 ms 9800 KB Output is correct
16 Correct 60 ms 6984 KB Output is correct
17 Correct 84 ms 10312 KB Output is correct
18 Correct 80 ms 9720 KB Output is correct
19 Correct 89 ms 10312 KB Output is correct
20 Correct 79 ms 9804 KB Output is correct
21 Correct 330 ms 68044 KB Output is correct
22 Correct 464 ms 89360 KB Output is correct
23 Correct 390 ms 87184 KB Output is correct
24 Correct 398 ms 84780 KB Output is correct
25 Correct 608 ms 86828 KB Output is correct
26 Correct 500 ms 88372 KB Output is correct
27 Correct 256 ms 67956 KB Output is correct
28 Correct 491 ms 88364 KB Output is correct
29 Correct 220 ms 73164 KB Output is correct
30 Correct 183 ms 72648 KB Output is correct
31 Correct 208 ms 74440 KB Output is correct
32 Correct 190 ms 74064 KB Output is correct
33 Correct 495 ms 73432 KB Output is correct
34 Correct 470 ms 73260 KB Output is correct
35 Correct 366 ms 64820 KB Output is correct
36 Correct 339 ms 67016 KB Output is correct
37 Correct 296 ms 67276 KB Output is correct
38 Correct 292 ms 62840 KB Output is correct
39 Correct 392 ms 81452 KB Output is correct
40 Correct 333 ms 52264 KB Output is correct
41 Correct 310 ms 57240 KB Output is correct
42 Correct 451 ms 73948 KB Output is correct
43 Correct 347 ms 56180 KB Output is correct
44 Correct 383 ms 58360 KB Output is correct
45 Correct 190 ms 68168 KB Output is correct
46 Correct 154 ms 62360 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 983 ms 53820 KB Output is correct
4 Correct 948 ms 56276 KB Output is correct
5 Correct 966 ms 56292 KB Output is correct
6 Correct 942 ms 55244 KB Output is correct
7 Correct 956 ms 56092 KB Output is correct
8 Correct 479 ms 30984 KB Output is correct
9 Correct 110 ms 56516 KB Output is correct
10 Execution timed out 3061 ms 28400 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 50 ms 5724 KB Output is correct
3 Correct 64 ms 8272 KB Output is correct
4 Correct 84 ms 10320 KB Output is correct
5 Correct 77 ms 8604 KB Output is correct
6 Correct 88 ms 10432 KB Output is correct
7 Correct 88 ms 10572 KB Output is correct
8 Correct 67 ms 8100 KB Output is correct
9 Correct 96 ms 10312 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 127 ms 9424 KB Output is correct
12 Correct 121 ms 9552 KB Output is correct
13 Correct 117 ms 9544 KB Output is correct
14 Correct 126 ms 9288 KB Output is correct
15 Correct 86 ms 9800 KB Output is correct
16 Correct 60 ms 6984 KB Output is correct
17 Correct 84 ms 10312 KB Output is correct
18 Correct 80 ms 9720 KB Output is correct
19 Correct 89 ms 10312 KB Output is correct
20 Correct 79 ms 9804 KB Output is correct
21 Correct 330 ms 68044 KB Output is correct
22 Correct 464 ms 89360 KB Output is correct
23 Correct 390 ms 87184 KB Output is correct
24 Correct 398 ms 84780 KB Output is correct
25 Correct 608 ms 86828 KB Output is correct
26 Correct 500 ms 88372 KB Output is correct
27 Correct 256 ms 67956 KB Output is correct
28 Correct 491 ms 88364 KB Output is correct
29 Correct 220 ms 73164 KB Output is correct
30 Correct 183 ms 72648 KB Output is correct
31 Correct 208 ms 74440 KB Output is correct
32 Correct 190 ms 74064 KB Output is correct
33 Correct 495 ms 73432 KB Output is correct
34 Correct 470 ms 73260 KB Output is correct
35 Correct 366 ms 64820 KB Output is correct
36 Correct 339 ms 67016 KB Output is correct
37 Correct 296 ms 67276 KB Output is correct
38 Correct 292 ms 62840 KB Output is correct
39 Correct 392 ms 81452 KB Output is correct
40 Correct 333 ms 52264 KB Output is correct
41 Correct 310 ms 57240 KB Output is correct
42 Correct 451 ms 73948 KB Output is correct
43 Correct 347 ms 56180 KB Output is correct
44 Correct 383 ms 58360 KB Output is correct
45 Correct 190 ms 68168 KB Output is correct
46 Correct 154 ms 62360 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 983 ms 53820 KB Output is correct
50 Correct 948 ms 56276 KB Output is correct
51 Correct 966 ms 56292 KB Output is correct
52 Correct 942 ms 55244 KB Output is correct
53 Correct 956 ms 56092 KB Output is correct
54 Correct 479 ms 30984 KB Output is correct
55 Correct 110 ms 56516 KB Output is correct
56 Execution timed out 3061 ms 28400 KB Time limit exceeded
57 Halted 0 ms 0 KB -