oj.uz

Submission #1108721

# Submission time Handle Problem Language Result Execution time Memory
1108721 2024-11-04T20:36:06 Z vladilius Escape Route 2 (JOI24_escape2) C++17
14 / 100
 875 ms 1048576 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 = 1;
    vector<int> all;
    pair<int, ll> st[M], nw[M];
    ll out[n / 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 5 ms 6480 KB Output is correct
2 Correct 43 ms 9512 KB Output is correct
3 Correct 84 ms 24904 KB Output is correct
4 Correct 101 ms 42312 KB Output is correct
5 Correct 93 ms 41288 KB Output is correct
6 Correct 102 ms 42360 KB Output is correct
7 Correct 116 ms 42316 KB Output is correct
8 Correct 71 ms 24904 KB Output is correct
9 Correct 107 ms 42336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6480 KB Output is correct
2 Correct 43 ms 9512 KB Output is correct
3 Correct 84 ms 24904 KB Output is correct
4 Correct 101 ms 42312 KB Output is correct
5 Correct 93 ms 41288 KB Output is correct
6 Correct 102 ms 42360 KB Output is correct
7 Correct 116 ms 42316 KB Output is correct
8 Correct 71 ms 24904 KB Output is correct
9 Correct 107 ms 42336 KB Output is correct
10 Correct 8 ms 6480 KB Output is correct
11 Correct 67 ms 11560 KB Output is correct
12 Correct 70 ms 11508 KB Output is correct
13 Correct 74 ms 11592 KB Output is correct
14 Correct 80 ms 11720 KB Output is correct
15 Correct 71 ms 13640 KB Output is correct
16 Correct 42 ms 9552 KB Output is correct
17 Correct 89 ms 24848 KB Output is correct
18 Correct 70 ms 14420 KB Output is correct
19 Correct 87 ms 24904 KB Output is correct
20 Correct 83 ms 14416 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6480 KB Output is correct
2 Correct 43 ms 9512 KB Output is correct
3 Correct 84 ms 24904 KB Output is correct
4 Correct 101 ms 42312 KB Output is correct
5 Correct 93 ms 41288 KB Output is correct
6 Correct 102 ms 42360 KB Output is correct
7 Correct 116 ms 42316 KB Output is correct
8 Correct 71 ms 24904 KB Output is correct
9 Correct 107 ms 42336 KB Output is correct
10 Runtime error 850 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6480 KB Output is correct
2 Correct 43 ms 9512 KB Output is correct
3 Correct 84 ms 24904 KB Output is correct
4 Correct 101 ms 42312 KB Output is correct
5 Correct 93 ms 41288 KB Output is correct
6 Correct 102 ms 42360 KB Output is correct
7 Correct 116 ms 42316 KB Output is correct
8 Correct 71 ms 24904 KB Output is correct
9 Correct 107 ms 42336 KB Output is correct
10 Correct 8 ms 6480 KB Output is correct
11 Correct 67 ms 11560 KB Output is correct
12 Correct 70 ms 11508 KB Output is correct
13 Correct 74 ms 11592 KB Output is correct
14 Correct 80 ms 11720 KB Output is correct
15 Correct 71 ms 13640 KB Output is correct
16 Correct 42 ms 9552 KB Output is correct
17 Correct 89 ms 24848 KB Output is correct
18 Correct 70 ms 14420 KB Output is correct
19 Correct 87 ms 24904 KB Output is correct
20 Correct 83 ms 14416 KB Output is correct
21 Runtime error 850 ms 1048576 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6480 KB Output is correct
2 Correct 6 ms 6480 KB Output is correct
3 Correct 123 ms 24572 KB Output is correct
4 Correct 126 ms 24648 KB Output is correct
5 Correct 148 ms 24512 KB Output is correct
6 Correct 124 ms 24576 KB Output is correct
7 Correct 123 ms 24392 KB Output is correct
8 Correct 55 ms 16968 KB Output is correct
9 Correct 73 ms 24904 KB Output is correct
10 Correct 47 ms 15452 KB Output is correct
11 Runtime error 875 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6480 KB Output is correct
2 Correct 43 ms 9512 KB Output is correct
3 Correct 84 ms 24904 KB Output is correct
4 Correct 101 ms 42312 KB Output is correct
5 Correct 93 ms 41288 KB Output is correct
6 Correct 102 ms 42360 KB Output is correct
7 Correct 116 ms 42316 KB Output is correct
8 Correct 71 ms 24904 KB Output is correct
9 Correct 107 ms 42336 KB Output is correct
10 Correct 8 ms 6480 KB Output is correct
11 Correct 67 ms 11560 KB Output is correct
12 Correct 70 ms 11508 KB Output is correct
13 Correct 74 ms 11592 KB Output is correct
14 Correct 80 ms 11720 KB Output is correct
15 Correct 71 ms 13640 KB Output is correct
16 Correct 42 ms 9552 KB Output is correct
17 Correct 89 ms 24848 KB Output is correct
18 Correct 70 ms 14420 KB Output is correct
19 Correct 87 ms 24904 KB Output is correct
20 Correct 83 ms 14416 KB Output is correct
21 Runtime error 850 ms 1048576 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -