oj.uz

Submission #1108722

# Submission time Handle Problem Language Result Execution time Memory
1108722 2024-11-04T20:38:45 Z vladilius Escape Route 2 (JOI24_escape2) C++17
54 / 100
 816 ms 147016 KB 
#include <bits/stdc++.h>
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 = 2e5;

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[n / A + 2][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 6 ms 6480 KB Output is correct
2 Correct 43 ms 9716 KB Output is correct
3 Correct 56 ms 9808 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 66 ms 10056 KB Output is correct
6 Correct 80 ms 10828 KB Output is correct
7 Correct 82 ms 11080 KB Output is correct
8 Correct 58 ms 9868 KB Output is correct
9 Correct 78 ms 10824 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 43 ms 9716 KB Output is correct
3 Correct 56 ms 9808 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 66 ms 10056 KB Output is correct
6 Correct 80 ms 10828 KB Output is correct
7 Correct 82 ms 11080 KB Output is correct
8 Correct 58 ms 9868 KB Output is correct
9 Correct 78 ms 10824 KB Output is correct
10 Correct 5 ms 6480 KB Output is correct
11 Correct 86 ms 10432 KB Output is correct
12 Correct 87 ms 10320 KB Output is correct
13 Correct 84 ms 10320 KB Output is correct
14 Correct 84 ms 10312 KB Output is correct
15 Correct 80 ms 10704 KB Output is correct
16 Correct 45 ms 9544 KB Output is correct
17 Correct 76 ms 10824 KB Output is correct
18 Correct 81 ms 10568 KB Output is correct
19 Correct 86 ms 10824 KB Output is correct
20 Correct 75 ms 10568 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 43 ms 9716 KB Output is correct
3 Correct 56 ms 9808 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 66 ms 10056 KB Output is correct
6 Correct 80 ms 10828 KB Output is correct
7 Correct 82 ms 11080 KB Output is correct
8 Correct 58 ms 9868 KB Output is correct
9 Correct 78 ms 10824 KB Output is correct
10 Correct 342 ms 98376 KB Output is correct
11 Correct 552 ms 146952 KB Output is correct
12 Correct 452 ms 147016 KB Output is correct
13 Correct 363 ms 145808 KB Output is correct
14 Correct 403 ms 146912 KB Output is correct
15 Correct 388 ms 146760 KB Output is correct
16 Correct 253 ms 98372 KB Output is correct
17 Correct 396 ms 146732 KB Output is correct
18 Correct 207 ms 120396 KB Output is correct
19 Correct 193 ms 120220 KB Output is correct
20 Correct 226 ms 120392 KB Output is correct
21 Correct 221 ms 120228 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 43 ms 9716 KB Output is correct
3 Correct 56 ms 9808 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 66 ms 10056 KB Output is correct
6 Correct 80 ms 10828 KB Output is correct
7 Correct 82 ms 11080 KB Output is correct
8 Correct 58 ms 9868 KB Output is correct
9 Correct 78 ms 10824 KB Output is correct
10 Correct 5 ms 6480 KB Output is correct
11 Correct 86 ms 10432 KB Output is correct
12 Correct 87 ms 10320 KB Output is correct
13 Correct 84 ms 10320 KB Output is correct
14 Correct 84 ms 10312 KB Output is correct
15 Correct 80 ms 10704 KB Output is correct
16 Correct 45 ms 9544 KB Output is correct
17 Correct 76 ms 10824 KB Output is correct
18 Correct 81 ms 10568 KB Output is correct
19 Correct 86 ms 10824 KB Output is correct
20 Correct 75 ms 10568 KB Output is correct
21 Correct 342 ms 98376 KB Output is correct
22 Correct 552 ms 146952 KB Output is correct
23 Correct 452 ms 147016 KB Output is correct
24 Correct 363 ms 145808 KB Output is correct
25 Correct 403 ms 146912 KB Output is correct
26 Correct 388 ms 146760 KB Output is correct
27 Correct 253 ms 98372 KB Output is correct
28 Correct 396 ms 146732 KB Output is correct
29 Correct 207 ms 120396 KB Output is correct
30 Correct 193 ms 120220 KB Output is correct
31 Correct 226 ms 120392 KB Output is correct
32 Correct 221 ms 120228 KB Output is correct
33 Correct 349 ms 34376 KB Output is correct
34 Correct 327 ms 34376 KB Output is correct
35 Correct 246 ms 32328 KB Output is correct
36 Correct 286 ms 32436 KB Output is correct
37 Correct 254 ms 38872 KB Output is correct
38 Correct 261 ms 57672 KB Output is correct
39 Correct 294 ms 82760 KB Output is correct
40 Correct 225 ms 29768 KB Output is correct
41 Correct 221 ms 52296 KB Output is correct
42 Correct 333 ms 80716 KB Output is correct
43 Correct 208 ms 36804 KB Output is correct
44 Correct 261 ms 38216 KB Output is correct
45 Correct 167 ms 67656 KB Output is correct
46 Correct 118 ms 35656 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 5 ms 6528 KB Output is correct
3 Correct 743 ms 23880 KB Output is correct
4 Correct 784 ms 23928 KB Output is correct
5 Correct 816 ms 23696 KB Output is correct
6 Correct 772 ms 23864 KB Output is correct
7 Correct 807 ms 23784 KB Output is correct
8 Correct 316 ms 16308 KB Output is correct
9 Correct 608 ms 24184 KB Output is correct
10 Correct 47 ms 15332 KB Output is correct
11 Correct 227 ms 122952 KB Output is correct
12 Correct 171 ms 70720 KB Output is correct
13 Correct 124 ms 38008 KB Output is correct
14 Correct 105 ms 30792 KB Output is correct
15 Correct 96 ms 28928 KB Output is correct
16 Correct 94 ms 31060 KB Output is correct
17 Runtime error 85 ms 58464 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 43 ms 9716 KB Output is correct
3 Correct 56 ms 9808 KB Output is correct
4 Correct 75 ms 11016 KB Output is correct
5 Correct 66 ms 10056 KB Output is correct
6 Correct 80 ms 10828 KB Output is correct
7 Correct 82 ms 11080 KB Output is correct
8 Correct 58 ms 9868 KB Output is correct
9 Correct 78 ms 10824 KB Output is correct
10 Correct 5 ms 6480 KB Output is correct
11 Correct 86 ms 10432 KB Output is correct
12 Correct 87 ms 10320 KB Output is correct
13 Correct 84 ms 10320 KB Output is correct
14 Correct 84 ms 10312 KB Output is correct
15 Correct 80 ms 10704 KB Output is correct
16 Correct 45 ms 9544 KB Output is correct
17 Correct 76 ms 10824 KB Output is correct
18 Correct 81 ms 10568 KB Output is correct
19 Correct 86 ms 10824 KB Output is correct
20 Correct 75 ms 10568 KB Output is correct
21 Correct 342 ms 98376 KB Output is correct
22 Correct 552 ms 146952 KB Output is correct
23 Correct 452 ms 147016 KB Output is correct
24 Correct 363 ms 145808 KB Output is correct
25 Correct 403 ms 146912 KB Output is correct
26 Correct 388 ms 146760 KB Output is correct
27 Correct 253 ms 98372 KB Output is correct
28 Correct 396 ms 146732 KB Output is correct
29 Correct 207 ms 120396 KB Output is correct
30 Correct 193 ms 120220 KB Output is correct
31 Correct 226 ms 120392 KB Output is correct
32 Correct 221 ms 120228 KB Output is correct
33 Correct 349 ms 34376 KB Output is correct
34 Correct 327 ms 34376 KB Output is correct
35 Correct 246 ms 32328 KB Output is correct
36 Correct 286 ms 32436 KB Output is correct
37 Correct 254 ms 38872 KB Output is correct
38 Correct 261 ms 57672 KB Output is correct
39 Correct 294 ms 82760 KB Output is correct
40 Correct 225 ms 29768 KB Output is correct
41 Correct 221 ms 52296 KB Output is correct
42 Correct 333 ms 80716 KB Output is correct
43 Correct 208 ms 36804 KB Output is correct
44 Correct 261 ms 38216 KB Output is correct
45 Correct 167 ms 67656 KB Output is correct
46 Correct 118 ms 35656 KB Output is correct
47 Correct 6 ms 6480 KB Output is correct
48 Correct 5 ms 6528 KB Output is correct
49 Correct 743 ms 23880 KB Output is correct
50 Correct 784 ms 23928 KB Output is correct
51 Correct 816 ms 23696 KB Output is correct
52 Correct 772 ms 23864 KB Output is correct
53 Correct 807 ms 23784 KB Output is correct
54 Correct 316 ms 16308 KB Output is correct
55 Correct 608 ms 24184 KB Output is correct
56 Correct 47 ms 15332 KB Output is correct
57 Correct 227 ms 122952 KB Output is correct
58 Correct 171 ms 70720 KB Output is correct
59 Correct 124 ms 38008 KB Output is correct
60 Correct 105 ms 30792 KB Output is correct
61 Correct 96 ms 28928 KB Output is correct
62 Correct 94 ms 31060 KB Output is correct
63 Runtime error 85 ms 58464 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -