oj.uz

Submission #1108654

# Submission time Handle Problem Language Result Execution time Memory
1108654 2024-11-04T17:58:00 Z vladilius Escape Route 2 (JOI24_escape2) C++17
6 / 100
 3000 ms 8308 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();

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();
            }
            nw.push_back(t[i][j]);
        }
        
        t[i] = nw;
    }
    
    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;
        pii mn = {1e9, 0};
        for (int j = x[i] - 1; j >= 0; j--){
            while (k >= 0 && t[i + 1][k].ff >= t[i][j].ss){
                mn = min(mn, {t[i + 1][k].ss, k});
                k--;
            }
            g[p[i - 1] + j] = p[i] + mn.ss;
            e[p[i - 1] + j] = (mn.ff == 1e9);
        }
    }
    
    for (int i = 0; i < x.back(); i++) g[p[n - 2] + i] = p[n - 2] + i;
    
    auto get = [&](int l, int r){
        ll out = inf;
        for (int i = 0; i < x[l]; i++){
            int tt = r - l - 1, x = p[l - 1] + i, cc = 0;
            while (tt--){
                cc += e[x];
                x = g[x];
            }
            out = min(out, 1LL * D * cc + (t[r - 1][x - p[r - 2]].ss - t[l][i].ff));
        }
        return out;
    };
    
    int q; cin>>q;
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        cout<<get(l, r)<<"\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 4464 KB Output is correct
3 Correct 250 ms 5460 KB Output is correct
4 Correct 446 ms 7300 KB Output is correct
5 Correct 355 ms 5700 KB Output is correct
6 Correct 443 ms 6984 KB Output is correct
7 Correct 446 ms 6984 KB Output is correct
8 Correct 256 ms 5452 KB Output is correct
9 Correct 459 ms 7048 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 4464 KB Output is correct
3 Correct 250 ms 5460 KB Output is correct
4 Correct 446 ms 7300 KB Output is correct
5 Correct 355 ms 5700 KB Output is correct
6 Correct 443 ms 6984 KB Output is correct
7 Correct 446 ms 6984 KB Output is correct
8 Correct 256 ms 5452 KB Output is correct
9 Correct 459 ms 7048 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 429 ms 6228 KB Output is correct
12 Correct 430 ms 6012 KB Output is correct
13 Correct 394 ms 6056 KB Output is correct
14 Correct 395 ms 6040 KB Output is correct
15 Correct 407 ms 6552 KB Output is correct
16 Correct 39 ms 4424 KB Output is correct
17 Correct 379 ms 6728 KB Output is correct
18 Correct 403 ms 6472 KB Output is correct
19 Correct 450 ms 6728 KB Output is correct
20 Incorrect 435 ms 6472 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 4464 KB Output is correct
3 Correct 250 ms 5460 KB Output is correct
4 Correct 446 ms 7300 KB Output is correct
5 Correct 355 ms 5700 KB Output is correct
6 Correct 443 ms 6984 KB Output is correct
7 Correct 446 ms 6984 KB Output is correct
8 Correct 256 ms 5452 KB Output is correct
9 Correct 459 ms 7048 KB Output is correct
10 Execution timed out 3045 ms 8308 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 4464 KB Output is correct
3 Correct 250 ms 5460 KB Output is correct
4 Correct 446 ms 7300 KB Output is correct
5 Correct 355 ms 5700 KB Output is correct
6 Correct 443 ms 6984 KB Output is correct
7 Correct 446 ms 6984 KB Output is correct
8 Correct 256 ms 5452 KB Output is correct
9 Correct 459 ms 7048 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 429 ms 6228 KB Output is correct
12 Correct 430 ms 6012 KB Output is correct
13 Correct 394 ms 6056 KB Output is correct
14 Correct 395 ms 6040 KB Output is correct
15 Correct 407 ms 6552 KB Output is correct
16 Correct 39 ms 4424 KB Output is correct
17 Correct 379 ms 6728 KB Output is correct
18 Correct 403 ms 6472 KB Output is correct
19 Correct 450 ms 6728 KB Output is correct
20 Incorrect 435 ms 6472 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Execution timed out 3077 ms 4752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 42 ms 4464 KB Output is correct
3 Correct 250 ms 5460 KB Output is correct
4 Correct 446 ms 7300 KB Output is correct
5 Correct 355 ms 5700 KB Output is correct
6 Correct 443 ms 6984 KB Output is correct
7 Correct 446 ms 6984 KB Output is correct
8 Correct 256 ms 5452 KB Output is correct
9 Correct 459 ms 7048 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 429 ms 6228 KB Output is correct
12 Correct 430 ms 6012 KB Output is correct
13 Correct 394 ms 6056 KB Output is correct
14 Correct 395 ms 6040 KB Output is correct
15 Correct 407 ms 6552 KB Output is correct
16 Correct 39 ms 4424 KB Output is correct
17 Correct 379 ms 6728 KB Output is correct
18 Correct 403 ms 6472 KB Output is correct
19 Correct 450 ms 6728 KB Output is correct
20 Incorrect 435 ms 6472 KB Output isn't correct
21 Halted 0 ms 0 KB -