oj.uz

Submission #1108725

# Submission time Handle Problem Language Result Execution time Memory
1108725 2024-11-04T20:45:59 Z vladilius Escape Route 2 (JOI24_escape2) C++17
100 / 100
 2100 ms 191608 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();
const int M = 1e5;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, D; cin>>n>>D;
    vector<int> x(n);
    vector<pii> t[n];
    for (int i = 1; i < n; i++){
        cin>>x[i];
        for (int j = 0; j < x[i]; j++){
            int a, b; cin>>a>>b;
            t[i].pb({a, b});
        }
    }
    
    for (int i = 1; i < n; i++){
        sort(t[i].begin(), t[i].end());
        vector<pii> nw;
        for (int j = 0; j < x[i]; j++){
            while (!nw.empty() && nw.back().ss >= t[i][j].ss){
                nw.pop_back();
            }
            if (nw.empty() || nw.back().ff != t[i][j].ff){
                nw.pb(t[i][j]);
            }
        }
        
        t[i] = nw;
        x[i] = (int) t[i].size();
    }
    
    vector<int> p(n);
    for (int i = 1; i < n; i++){
        p[i] = p[i - 1] + x[i];
    }
    int S = p.back();
    vector<int> g(S);
    vector<bool> e(S);
    for (int i = 1; i + 1 < n; i++){
        int k = x[i + 1] - 1, mn = 0;
        for (int j = x[i] - 1; j >= 0; j--){
            while (k >= 0 && t[i + 1][k].ff >= t[i][j].ss){
                mn = k--;
            }
            g[p[i - 1] + j] = p[i] + mn;
            e[p[i - 1] + j] = (t[i][j].ss > t[i + 1][mn].ff);
        }
    }
    
    const int lg = log2(S);
    vector<vector<pii>> sp(S, vector<pii>(lg + 1));
    for (int i = 0; i < S; i++) sp[i][0] = {g[i], e[i]};
    for (int j = 1; j <= lg; j++){
        for (int i = 0; i + (1 << j) <= S; i++){
            sp[i][j] = {sp[sp[i][j - 1].ff][j - 1].ff, sp[i][j - 1].ss + sp[sp[i][j - 1].ff][j - 1].ss};
        }
    }
    
    auto get = [&](int l, int r){
        ll out = inf;
        for (int i = 0; i < x[l]; i++){
            int tt = r - l - 1, f = p[l - 1] + i, cc = 0;
            for (int j = lg; j >= 0; j--){
                int k = (1 << j);
                if (tt >= k){
                    cc += sp[f][j].ss;
                    f = sp[f][j].ff;
                    tt -= k;
                }
            }
            out = min(out, 1LL * D * cc + (t[r - 1][f - p[r - 2]].ss - t[l][i].ff));
        }
        return out;
    };
    
    const int A = 500;
    vector<int> all;
    pair<int, ll> st[M], nw[M];
    ll out[M / A + 5][n + 1];
    int s1 = 0, s2 = 0, cc = 0;
    ll mn;
    for (int i = 1; i < n; i++){
        if (x[i] <= A) continue;
        all.pb(i);
        s1 = s2 = 0;
        for (int j = 0; j < x[i]; j++){
            st[s1++] = {p[i - 1] + j, t[i][j].ss - t[i][j].ff};
        }
        for (int j = i + 1; j <= n; j++){
            mn = inf;
            for (int k = 0; k < s1; k++){
                mn = min(mn, st[k].ss);
            }
            out[cc][j] = mn;
            if (j == n) break;
            for (int k = 0; k < s1; k++){
                auto &[x, y] = st[k];
                y += D * e[x] + (t[j][g[x] - p[j - 1]].ss - t[j - 1][x - p[j - 2]].ss);
                x = g[x];
            }
            s2 = 0;
            int k = 0;
            while (k < s1){
                int h = k; mn = inf;
                while (h < s1 && st[k].ff == st[h].ff){
                    mn = min(mn, st[h].ss);
                    h++;
                }
                nw[s2++] = {st[k].ff, mn};
                k = h;
            }
            s1 = s2;
            for (int i = 0; i < s1; i++){
                st[i] = nw[i];
            }
        }
        cc++;
    }
    
    vector<int> :: iterator it;
    int q; cin>>q;
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        if (x[l] <= A){
            cout<<get(l, r)<<"\n";
        }
        else {
            it = lower_bound(all.begin(), all.end(), l);
            int j = (int) (it - all.begin());
            cout<<out[j][r]<<"\n";
        }
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 52 ms 6528 KB Output is correct
3 Correct 60 ms 9032 KB Output is correct
4 Correct 76 ms 11080 KB Output is correct
5 Correct 73 ms 10024 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 80 ms 11080 KB Output is correct
8 Correct 60 ms 9048 KB Output is correct
9 Correct 82 ms 11080 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 52 ms 6528 KB Output is correct
3 Correct 60 ms 9032 KB Output is correct
4 Correct 76 ms 11080 KB Output is correct
5 Correct 73 ms 10024 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 80 ms 11080 KB Output is correct
8 Correct 60 ms 9048 KB Output is correct
9 Correct 82 ms 11080 KB Output is correct
10 Correct 4 ms 3408 KB Output is correct
11 Correct 81 ms 8008 KB Output is correct
12 Correct 75 ms 7752 KB Output is correct
13 Correct 78 ms 7816 KB Output is correct
14 Correct 85 ms 7752 KB Output is correct
15 Correct 74 ms 8520 KB Output is correct
16 Correct 42 ms 6436 KB Output is correct
17 Correct 73 ms 9884 KB Output is correct
18 Correct 72 ms 8616 KB Output is correct
19 Correct 83 ms 9800 KB Output is correct
20 Correct 71 ms 8520 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 52 ms 6528 KB Output is correct
3 Correct 60 ms 9032 KB Output is correct
4 Correct 76 ms 11080 KB Output is correct
5 Correct 73 ms 10024 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 80 ms 11080 KB Output is correct
8 Correct 60 ms 9048 KB Output is correct
9 Correct 82 ms 11080 KB Output is correct
10 Correct 357 ms 151384 KB Output is correct
11 Correct 437 ms 191544 KB Output is correct
12 Correct 422 ms 191608 KB Output is correct
13 Correct 347 ms 190288 KB Output is correct
14 Correct 384 ms 191592 KB Output is correct
15 Correct 452 ms 191560 KB Output is correct
16 Correct 286 ms 151368 KB Output is correct
17 Correct 372 ms 191568 KB Output is correct
18 Correct 270 ms 170048 KB Output is correct
19 Correct 212 ms 169800 KB Output is correct
20 Correct 231 ms 170052 KB Output is correct
21 Correct 239 ms 169996 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 52 ms 6528 KB Output is correct
3 Correct 60 ms 9032 KB Output is correct
4 Correct 76 ms 11080 KB Output is correct
5 Correct 73 ms 10024 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 80 ms 11080 KB Output is correct
8 Correct 60 ms 9048 KB Output is correct
9 Correct 82 ms 11080 KB Output is correct
10 Correct 4 ms 3408 KB Output is correct
11 Correct 81 ms 8008 KB Output is correct
12 Correct 75 ms 7752 KB Output is correct
13 Correct 78 ms 7816 KB Output is correct
14 Correct 85 ms 7752 KB Output is correct
15 Correct 74 ms 8520 KB Output is correct
16 Correct 42 ms 6436 KB Output is correct
17 Correct 73 ms 9884 KB Output is correct
18 Correct 72 ms 8616 KB Output is correct
19 Correct 83 ms 9800 KB Output is correct
20 Correct 71 ms 8520 KB Output is correct
21 Correct 357 ms 151384 KB Output is correct
22 Correct 437 ms 191544 KB Output is correct
23 Correct 422 ms 191608 KB Output is correct
24 Correct 347 ms 190288 KB Output is correct
25 Correct 384 ms 191592 KB Output is correct
26 Correct 452 ms 191560 KB Output is correct
27 Correct 286 ms 151368 KB Output is correct
28 Correct 372 ms 191568 KB Output is correct
29 Correct 270 ms 170048 KB Output is correct
30 Correct 212 ms 169800 KB Output is correct
31 Correct 231 ms 170052 KB Output is correct
32 Correct 239 ms 169996 KB Output is correct
33 Correct 333 ms 58692 KB Output is correct
34 Correct 338 ms 58472 KB Output is correct
35 Correct 263 ms 56576 KB Output is correct
36 Correct 256 ms 56564 KB Output is correct
37 Correct 290 ms 73712 KB Output is correct
38 Correct 284 ms 107336 KB Output is correct
39 Correct 376 ms 135856 KB Output is correct
40 Correct 297 ms 56648 KB Output is correct
41 Correct 242 ms 100936 KB Output is correct
42 Correct 326 ms 133676 KB Output is correct
43 Correct 221 ms 73848 KB Output is correct
44 Correct 277 ms 75844 KB Output is correct
45 Correct 203 ms 120040 KB Output is correct
46 Correct 154 ms 70532 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 512 ms 21320 KB Output is correct
4 Correct 586 ms 21288 KB Output is correct
5 Correct 555 ms 21268 KB Output is correct
6 Correct 506 ms 21064 KB Output is correct
7 Correct 511 ms 21444 KB Output is correct
8 Correct 232 ms 13640 KB Output is correct
9 Correct 52 ms 21320 KB Output is correct
10 Correct 43 ms 12416 KB Output is correct
11 Correct 266 ms 170084 KB Output is correct
12 Correct 227 ms 120136 KB Output is correct
13 Correct 153 ms 70472 KB Output is correct
14 Correct 100 ms 52040 KB Output is correct
15 Correct 105 ms 51884 KB Output is correct
16 Correct 102 ms 52560 KB Output is correct
17 Correct 112 ms 52040 KB Output is correct
18 Correct 105 ms 22976 KB Output is correct
19 Correct 409 ms 21424 KB Output is correct
20 Correct 543 ms 129608 KB Output is correct
21 Correct 480 ms 129512 KB Output is correct
22 Correct 647 ms 75080 KB Output is correct
23 Correct 493 ms 75080 KB Output is correct
24 Correct 114 ms 74972 KB Output is correct
25 Correct 106 ms 74960 KB Output is correct
26 Correct 111 ms 75080 KB Output is correct
27 Correct 231 ms 169788 KB Output is correct
28 Correct 238 ms 170064 KB Output is correct
29 Correct 227 ms 170056 KB Output is correct
30 Correct 67 ms 16068 KB Output is correct
31 Correct 95 ms 5356 KB Output is correct
32 Correct 69 ms 12468 KB Output is correct
33 Correct 50 ms 5824 KB Output is correct
34 Correct 71 ms 7752 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 52 ms 6528 KB Output is correct
3 Correct 60 ms 9032 KB Output is correct
4 Correct 76 ms 11080 KB Output is correct
5 Correct 73 ms 10024 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 80 ms 11080 KB Output is correct
8 Correct 60 ms 9048 KB Output is correct
9 Correct 82 ms 11080 KB Output is correct
10 Correct 4 ms 3408 KB Output is correct
11 Correct 81 ms 8008 KB Output is correct
12 Correct 75 ms 7752 KB Output is correct
13 Correct 78 ms 7816 KB Output is correct
14 Correct 85 ms 7752 KB Output is correct
15 Correct 74 ms 8520 KB Output is correct
16 Correct 42 ms 6436 KB Output is correct
17 Correct 73 ms 9884 KB Output is correct
18 Correct 72 ms 8616 KB Output is correct
19 Correct 83 ms 9800 KB Output is correct
20 Correct 71 ms 8520 KB Output is correct
21 Correct 357 ms 151384 KB Output is correct
22 Correct 437 ms 191544 KB Output is correct
23 Correct 422 ms 191608 KB Output is correct
24 Correct 347 ms 190288 KB Output is correct
25 Correct 384 ms 191592 KB Output is correct
26 Correct 452 ms 191560 KB Output is correct
27 Correct 286 ms 151368 KB Output is correct
28 Correct 372 ms 191568 KB Output is correct
29 Correct 270 ms 170048 KB Output is correct
30 Correct 212 ms 169800 KB Output is correct
31 Correct 231 ms 170052 KB Output is correct
32 Correct 239 ms 169996 KB Output is correct
33 Correct 333 ms 58692 KB Output is correct
34 Correct 338 ms 58472 KB Output is correct
35 Correct 263 ms 56576 KB Output is correct
36 Correct 256 ms 56564 KB Output is correct
37 Correct 290 ms 73712 KB Output is correct
38 Correct 284 ms 107336 KB Output is correct
39 Correct 376 ms 135856 KB Output is correct
40 Correct 297 ms 56648 KB Output is correct
41 Correct 242 ms 100936 KB Output is correct
42 Correct 326 ms 133676 KB Output is correct
43 Correct 221 ms 73848 KB Output is correct
44 Correct 277 ms 75844 KB Output is correct
45 Correct 203 ms 120040 KB Output is correct
46 Correct 154 ms 70532 KB Output is correct
47 Correct 3 ms 3408 KB Output is correct
48 Correct 3 ms 3408 KB Output is correct
49 Correct 512 ms 21320 KB Output is correct
50 Correct 586 ms 21288 KB Output is correct
51 Correct 555 ms 21268 KB Output is correct
52 Correct 506 ms 21064 KB Output is correct
53 Correct 511 ms 21444 KB Output is correct
54 Correct 232 ms 13640 KB Output is correct
55 Correct 52 ms 21320 KB Output is correct
56 Correct 43 ms 12416 KB Output is correct
57 Correct 266 ms 170084 KB Output is correct
58 Correct 227 ms 120136 KB Output is correct
59 Correct 153 ms 70472 KB Output is correct
60 Correct 100 ms 52040 KB Output is correct
61 Correct 105 ms 51884 KB Output is correct
62 Correct 102 ms 52560 KB Output is correct
63 Correct 112 ms 52040 KB Output is correct
64 Correct 105 ms 22976 KB Output is correct
65 Correct 409 ms 21424 KB Output is correct
66 Correct 543 ms 129608 KB Output is correct
67 Correct 480 ms 129512 KB Output is correct
68 Correct 647 ms 75080 KB Output is correct
69 Correct 493 ms 75080 KB Output is correct
70 Correct 114 ms 74972 KB Output is correct
71 Correct 106 ms 74960 KB Output is correct
72 Correct 111 ms 75080 KB Output is correct
73 Correct 231 ms 169788 KB Output is correct
74 Correct 238 ms 170064 KB Output is correct
75 Correct 227 ms 170056 KB Output is correct
76 Correct 67 ms 16068 KB Output is correct
77 Correct 95 ms 5356 KB Output is correct
78 Correct 69 ms 12468 KB Output is correct
79 Correct 50 ms 5824 KB Output is correct
80 Correct 71 ms 7752 KB Output is correct
81 Correct 1314 ms 25416 KB Output is correct
82 Correct 1309 ms 25404 KB Output is correct
83 Correct 1310 ms 25160 KB Output is correct
84 Correct 1222 ms 25104 KB Output is correct
85 Correct 1284 ms 25136 KB Output is correct
86 Correct 514 ms 17116 KB Output is correct
87 Correct 932 ms 25988 KB Output is correct
88 Correct 1087 ms 26316 KB Output is correct
89 Correct 951 ms 26364 KB Output is correct
90 Correct 419 ms 18108 KB Output is correct
91 Correct 83 ms 13756 KB Output is correct
92 Correct 224 ms 61604 KB Output is correct
93 Correct 210 ms 60420 KB Output is correct
94 Correct 217 ms 60636 KB Output is correct
95 Correct 232 ms 60396 KB Output is correct
96 Correct 285 ms 27836 KB Output is correct
97 Correct 1299 ms 25928 KB Output is correct
98 Correct 1689 ms 134400 KB Output is correct
99 Correct 1369 ms 134424 KB Output is correct
100 Correct 2100 ms 79944 KB Output is correct
101 Correct 1618 ms 79912 KB Output is correct
102 Correct 182 ms 79780 KB Output is correct
103 Correct 150 ms 79824 KB Output is correct
104 Correct 203 ms 79944 KB Output is correct
105 Correct 108 ms 11384 KB Output is correct
106 Correct 174 ms 7616 KB Output is correct
107 Correct 187 ms 16104 KB Output is correct
108 Correct 135 ms 8712 KB Output is correct
109 Correct 190 ms 10568 KB Output is correct