oj.uz

Submission #1108726

# Submission time Handle Problem Language Result Execution time Memory
1108726 2024-11-04T20:47:36 Z vladilius Escape Route 2 (JOI24_escape2) C++17
100 / 100
 2040 ms 146192 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 = 700;
    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 42 ms 6536 KB Output is correct
3 Correct 55 ms 8276 KB Output is correct
4 Correct 74 ms 9968 KB Output is correct
5 Correct 67 ms 9288 KB Output is correct
6 Correct 76 ms 10064 KB Output is correct
7 Correct 78 ms 10076 KB Output is correct
8 Correct 55 ms 8264 KB Output is correct
9 Correct 76 ms 10152 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 42 ms 6536 KB Output is correct
3 Correct 55 ms 8276 KB Output is correct
4 Correct 74 ms 9968 KB Output is correct
5 Correct 67 ms 9288 KB Output is correct
6 Correct 76 ms 10064 KB Output is correct
7 Correct 78 ms 10076 KB Output is correct
8 Correct 55 ms 8264 KB Output is correct
9 Correct 76 ms 10152 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 79 ms 7640 KB Output is correct
12 Correct 78 ms 7764 KB Output is correct
13 Correct 85 ms 7752 KB Output is correct
14 Correct 82 ms 7752 KB Output is correct
15 Correct 70 ms 8264 KB Output is correct
16 Correct 40 ms 6472 KB Output is correct
17 Correct 74 ms 9148 KB Output is correct
18 Correct 73 ms 8264 KB Output is correct
19 Correct 76 ms 9032 KB Output is correct
20 Correct 69 ms 8280 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 42 ms 6536 KB Output is correct
3 Correct 55 ms 8276 KB Output is correct
4 Correct 74 ms 9968 KB Output is correct
5 Correct 67 ms 9288 KB Output is correct
6 Correct 76 ms 10064 KB Output is correct
7 Correct 78 ms 10076 KB Output is correct
8 Correct 55 ms 8264 KB Output is correct
9 Correct 76 ms 10152 KB Output is correct
10 Correct 284 ms 115528 KB Output is correct
11 Correct 398 ms 146192 KB Output is correct
12 Correct 404 ms 145992 KB Output is correct
13 Correct 303 ms 144968 KB Output is correct
14 Correct 342 ms 146004 KB Output is correct
15 Correct 334 ms 145992 KB Output is correct
16 Correct 243 ms 115528 KB Output is correct
17 Correct 333 ms 145988 KB Output is correct
18 Correct 201 ms 129204 KB Output is correct
19 Correct 181 ms 129096 KB Output is correct
20 Correct 192 ms 129096 KB Output is correct
21 Correct 189 ms 129096 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 42 ms 6536 KB Output is correct
3 Correct 55 ms 8276 KB Output is correct
4 Correct 74 ms 9968 KB Output is correct
5 Correct 67 ms 9288 KB Output is correct
6 Correct 76 ms 10064 KB Output is correct
7 Correct 78 ms 10076 KB Output is correct
8 Correct 55 ms 8264 KB Output is correct
9 Correct 76 ms 10152 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 79 ms 7640 KB Output is correct
12 Correct 78 ms 7764 KB Output is correct
13 Correct 85 ms 7752 KB Output is correct
14 Correct 82 ms 7752 KB Output is correct
15 Correct 70 ms 8264 KB Output is correct
16 Correct 40 ms 6472 KB Output is correct
17 Correct 74 ms 9148 KB Output is correct
18 Correct 73 ms 8264 KB Output is correct
19 Correct 76 ms 9032 KB Output is correct
20 Correct 69 ms 8280 KB Output is correct
21 Correct 284 ms 115528 KB Output is correct
22 Correct 398 ms 146192 KB Output is correct
23 Correct 404 ms 145992 KB Output is correct
24 Correct 303 ms 144968 KB Output is correct
25 Correct 342 ms 146004 KB Output is correct
26 Correct 334 ms 145992 KB Output is correct
27 Correct 243 ms 115528 KB Output is correct
28 Correct 333 ms 145988 KB Output is correct
29 Correct 201 ms 129204 KB Output is correct
30 Correct 181 ms 129096 KB Output is correct
31 Correct 192 ms 129096 KB Output is correct
32 Correct 189 ms 129096 KB Output is correct
33 Correct 291 ms 49648 KB Output is correct
34 Correct 318 ms 49528 KB Output is correct
35 Correct 283 ms 47432 KB Output is correct
36 Correct 258 ms 47432 KB Output is correct
37 Correct 254 ms 59976 KB Output is correct
38 Correct 289 ms 83528 KB Output is correct
39 Correct 336 ms 105544 KB Output is correct
40 Correct 258 ms 46408 KB Output is correct
41 Correct 242 ms 78408 KB Output is correct
42 Correct 326 ms 103552 KB Output is correct
43 Correct 216 ms 59040 KB Output is correct
44 Correct 256 ms 60584 KB Output is correct
45 Correct 180 ms 92924 KB Output is correct
46 Correct 148 ms 56892 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 583 ms 21076 KB Output is correct
4 Correct 539 ms 21064 KB Output is correct
5 Correct 536 ms 21064 KB Output is correct
6 Correct 550 ms 20956 KB Output is correct
7 Correct 498 ms 21052 KB Output is correct
8 Correct 229 ms 13640 KB Output is correct
9 Correct 407 ms 21396 KB Output is correct
10 Correct 41 ms 12260 KB Output is correct
11 Correct 216 ms 129252 KB Output is correct
12 Correct 184 ms 92752 KB Output is correct
13 Correct 163 ms 56904 KB Output is correct
14 Correct 92 ms 43528 KB Output is correct
15 Correct 99 ms 43264 KB Output is correct
16 Correct 100 ms 43848 KB Output is correct
17 Correct 104 ms 43592 KB Output is correct
18 Correct 108 ms 22208 KB Output is correct
19 Correct 441 ms 21316 KB Output is correct
20 Correct 539 ms 99676 KB Output is correct
21 Correct 451 ms 99656 KB Output is correct
22 Correct 637 ms 60232 KB Output is correct
23 Correct 455 ms 60296 KB Output is correct
24 Correct 93 ms 60124 KB Output is correct
25 Correct 86 ms 60016 KB Output is correct
26 Correct 96 ms 60232 KB Output is correct
27 Correct 188 ms 128828 KB Output is correct
28 Correct 192 ms 129104 KB Output is correct
29 Correct 187 ms 129096 KB Output is correct
30 Correct 72 ms 13704 KB Output is correct
31 Correct 87 ms 5380 KB Output is correct
32 Correct 70 ms 11588 KB Output is correct
33 Correct 55 ms 5820 KB Output is correct
34 Correct 69 ms 7496 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 42 ms 6536 KB Output is correct
3 Correct 55 ms 8276 KB Output is correct
4 Correct 74 ms 9968 KB Output is correct
5 Correct 67 ms 9288 KB Output is correct
6 Correct 76 ms 10064 KB Output is correct
7 Correct 78 ms 10076 KB Output is correct
8 Correct 55 ms 8264 KB Output is correct
9 Correct 76 ms 10152 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 79 ms 7640 KB Output is correct
12 Correct 78 ms 7764 KB Output is correct
13 Correct 85 ms 7752 KB Output is correct
14 Correct 82 ms 7752 KB Output is correct
15 Correct 70 ms 8264 KB Output is correct
16 Correct 40 ms 6472 KB Output is correct
17 Correct 74 ms 9148 KB Output is correct
18 Correct 73 ms 8264 KB Output is correct
19 Correct 76 ms 9032 KB Output is correct
20 Correct 69 ms 8280 KB Output is correct
21 Correct 284 ms 115528 KB Output is correct
22 Correct 398 ms 146192 KB Output is correct
23 Correct 404 ms 145992 KB Output is correct
24 Correct 303 ms 144968 KB Output is correct
25 Correct 342 ms 146004 KB Output is correct
26 Correct 334 ms 145992 KB Output is correct
27 Correct 243 ms 115528 KB Output is correct
28 Correct 333 ms 145988 KB Output is correct
29 Correct 201 ms 129204 KB Output is correct
30 Correct 181 ms 129096 KB Output is correct
31 Correct 192 ms 129096 KB Output is correct
32 Correct 189 ms 129096 KB Output is correct
33 Correct 291 ms 49648 KB Output is correct
34 Correct 318 ms 49528 KB Output is correct
35 Correct 283 ms 47432 KB Output is correct
36 Correct 258 ms 47432 KB Output is correct
37 Correct 254 ms 59976 KB Output is correct
38 Correct 289 ms 83528 KB Output is correct
39 Correct 336 ms 105544 KB Output is correct
40 Correct 258 ms 46408 KB Output is correct
41 Correct 242 ms 78408 KB Output is correct
42 Correct 326 ms 103552 KB Output is correct
43 Correct 216 ms 59040 KB Output is correct
44 Correct 256 ms 60584 KB Output is correct
45 Correct 180 ms 92924 KB Output is correct
46 Correct 148 ms 56892 KB Output is correct
47 Correct 4 ms 3408 KB Output is correct
48 Correct 3 ms 3408 KB Output is correct
49 Correct 583 ms 21076 KB Output is correct
50 Correct 539 ms 21064 KB Output is correct
51 Correct 536 ms 21064 KB Output is correct
52 Correct 550 ms 20956 KB Output is correct
53 Correct 498 ms 21052 KB Output is correct
54 Correct 229 ms 13640 KB Output is correct
55 Correct 407 ms 21396 KB Output is correct
56 Correct 41 ms 12260 KB Output is correct
57 Correct 216 ms 129252 KB Output is correct
58 Correct 184 ms 92752 KB Output is correct
59 Correct 163 ms 56904 KB Output is correct
60 Correct 92 ms 43528 KB Output is correct
61 Correct 99 ms 43264 KB Output is correct
62 Correct 100 ms 43848 KB Output is correct
63 Correct 104 ms 43592 KB Output is correct
64 Correct 108 ms 22208 KB Output is correct
65 Correct 441 ms 21316 KB Output is correct
66 Correct 539 ms 99676 KB Output is correct
67 Correct 451 ms 99656 KB Output is correct
68 Correct 637 ms 60232 KB Output is correct
69 Correct 455 ms 60296 KB Output is correct
70 Correct 93 ms 60124 KB Output is correct
71 Correct 86 ms 60016 KB Output is correct
72 Correct 96 ms 60232 KB Output is correct
73 Correct 188 ms 128828 KB Output is correct
74 Correct 192 ms 129104 KB Output is correct
75 Correct 187 ms 129096 KB Output is correct
76 Correct 72 ms 13704 KB Output is correct
77 Correct 87 ms 5380 KB Output is correct
78 Correct 70 ms 11588 KB Output is correct
79 Correct 55 ms 5820 KB Output is correct
80 Correct 69 ms 7496 KB Output is correct
81 Correct 1302 ms 25160 KB Output is correct
82 Correct 1246 ms 25160 KB Output is correct
83 Correct 1295 ms 24904 KB Output is correct
84 Correct 1258 ms 24904 KB Output is correct
85 Correct 1189 ms 24912 KB Output is correct
86 Correct 510 ms 17020 KB Output is correct
87 Correct 1022 ms 25848 KB Output is correct
88 Correct 1202 ms 25848 KB Output is correct
89 Correct 1112 ms 25928 KB Output is correct
90 Correct 417 ms 17920 KB Output is correct
91 Correct 66 ms 13752 KB Output is correct
92 Correct 188 ms 51616 KB Output is correct
93 Correct 212 ms 50948 KB Output is correct
94 Correct 185 ms 51016 KB Output is correct
95 Correct 208 ms 50760 KB Output is correct
96 Correct 272 ms 26920 KB Output is correct
97 Correct 1211 ms 25508 KB Output is correct
98 Correct 1605 ms 104580 KB Output is correct
99 Correct 1252 ms 104756 KB Output is correct
100 Correct 2040 ms 65060 KB Output is correct
101 Correct 1548 ms 65136 KB Output is correct
102 Correct 176 ms 64920 KB Output is correct
103 Correct 140 ms 64916 KB Output is correct
104 Correct 169 ms 64840 KB Output is correct
105 Correct 109 ms 10624 KB Output is correct
106 Correct 186 ms 7616 KB Output is correct
107 Correct 184 ms 15056 KB Output is correct
108 Correct 135 ms 8452 KB Output is correct
109 Correct 185 ms 10312 KB Output is correct