oj.uz

Submission #1108718

# Submission time Handle Problem Language Result Execution time Memory
1108718 2024-11-04T20:33:37 Z vladilius Escape Route 2 (JOI24_escape2) C++17
14 / 100
 951 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 = 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 = 1;
    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 4 ms 3408 KB Output is correct
2 Correct 40 ms 6420 KB Output is correct
3 Correct 64 ms 21832 KB Output is correct
4 Correct 118 ms 39240 KB Output is correct
5 Correct 85 ms 38216 KB Output is correct
6 Correct 99 ms 39104 KB Output is correct
7 Correct 97 ms 39244 KB Output is correct
8 Correct 66 ms 21848 KB Output is correct
9 Correct 104 ms 39180 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Output is correct
2 Correct 40 ms 6420 KB Output is correct
3 Correct 64 ms 21832 KB Output is correct
4 Correct 118 ms 39240 KB Output is correct
5 Correct 85 ms 38216 KB Output is correct
6 Correct 99 ms 39104 KB Output is correct
7 Correct 97 ms 39244 KB Output is correct
8 Correct 66 ms 21848 KB Output is correct
9 Correct 104 ms 39180 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 67 ms 8432 KB Output is correct
12 Correct 64 ms 8528 KB Output is correct
13 Correct 66 ms 8520 KB Output is correct
14 Correct 67 ms 8520 KB Output is correct
15 Correct 68 ms 10312 KB Output is correct
16 Correct 45 ms 6456 KB Output is correct
17 Correct 97 ms 21696 KB Output is correct
18 Correct 70 ms 11340 KB Output is correct
19 Correct 97 ms 21836 KB Output is correct
20 Correct 71 ms 11092 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Output is correct
2 Correct 40 ms 6420 KB Output is correct
3 Correct 64 ms 21832 KB Output is correct
4 Correct 118 ms 39240 KB Output is correct
5 Correct 85 ms 38216 KB Output is correct
6 Correct 99 ms 39104 KB Output is correct
7 Correct 97 ms 39244 KB Output is correct
8 Correct 66 ms 21848 KB Output is correct
9 Correct 104 ms 39180 KB Output is correct
10 Runtime error 951 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 4 ms 3408 KB Output is correct
2 Correct 40 ms 6420 KB Output is correct
3 Correct 64 ms 21832 KB Output is correct
4 Correct 118 ms 39240 KB Output is correct
5 Correct 85 ms 38216 KB Output is correct
6 Correct 99 ms 39104 KB Output is correct
7 Correct 97 ms 39244 KB Output is correct
8 Correct 66 ms 21848 KB Output is correct
9 Correct 104 ms 39180 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 67 ms 8432 KB Output is correct
12 Correct 64 ms 8528 KB Output is correct
13 Correct 66 ms 8520 KB Output is correct
14 Correct 67 ms 8520 KB Output is correct
15 Correct 68 ms 10312 KB Output is correct
16 Correct 45 ms 6456 KB Output is correct
17 Correct 97 ms 21696 KB Output is correct
18 Correct 70 ms 11340 KB Output is correct
19 Correct 97 ms 21836 KB Output is correct
20 Correct 71 ms 11092 KB Output is correct
21 Runtime error 951 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 4 ms 3408 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 129 ms 21436 KB Output is correct
4 Correct 128 ms 21320 KB Output is correct
5 Correct 132 ms 21320 KB Output is correct
6 Correct 136 ms 21312 KB Output is correct
7 Correct 128 ms 21320 KB Output is correct
8 Correct 50 ms 13900 KB Output is correct
9 Correct 59 ms 21588 KB Output is correct
10 Correct 42 ms 12552 KB Output is correct
11 Runtime error 931 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 4 ms 3408 KB Output is correct
2 Correct 40 ms 6420 KB Output is correct
3 Correct 64 ms 21832 KB Output is correct
4 Correct 118 ms 39240 KB Output is correct
5 Correct 85 ms 38216 KB Output is correct
6 Correct 99 ms 39104 KB Output is correct
7 Correct 97 ms 39244 KB Output is correct
8 Correct 66 ms 21848 KB Output is correct
9 Correct 104 ms 39180 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 67 ms 8432 KB Output is correct
12 Correct 64 ms 8528 KB Output is correct
13 Correct 66 ms 8520 KB Output is correct
14 Correct 67 ms 8520 KB Output is correct
15 Correct 68 ms 10312 KB Output is correct
16 Correct 45 ms 6456 KB Output is correct
17 Correct 97 ms 21696 KB Output is correct
18 Correct 70 ms 11340 KB Output is correct
19 Correct 97 ms 21836 KB Output is correct
20 Correct 71 ms 11092 KB Output is correct
21 Runtime error 951 ms 1048576 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -