oj.uz

Submission #1108690

# Submission time Handle Problem Language Result Execution time Memory
1108690 2024-11-04T19:11:18 Z vladilius Escape Route 2 (JOI24_escape2) C++17
14 / 100
 3000 ms 5960 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();
            }
            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);
        }
    }
    
    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;
            while (tt--){
                cc += e[f];
                f = g[f];
            }
            out = min(out, 1LL * D * cc + (t[r - 1][f - 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 37 ms 3356 KB Output is correct
3 Correct 254 ms 3400 KB Output is correct
4 Correct 442 ms 4396 KB Output is correct
5 Correct 345 ms 3400 KB Output is correct
6 Correct 449 ms 4424 KB Output is correct
7 Correct 453 ms 4424 KB Output is correct
8 Correct 262 ms 3292 KB Output is correct
9 Correct 445 ms 4360 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 37 ms 3356 KB Output is correct
3 Correct 254 ms 3400 KB Output is correct
4 Correct 442 ms 4396 KB Output is correct
5 Correct 345 ms 3400 KB Output is correct
6 Correct 449 ms 4424 KB Output is correct
7 Correct 453 ms 4424 KB Output is correct
8 Correct 262 ms 3292 KB Output is correct
9 Correct 445 ms 4360 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 432 ms 3912 KB Output is correct
12 Correct 430 ms 3824 KB Output is correct
13 Correct 405 ms 3912 KB Output is correct
14 Correct 395 ms 3916 KB Output is correct
15 Correct 398 ms 4168 KB Output is correct
16 Correct 51 ms 3400 KB Output is correct
17 Correct 386 ms 4216 KB Output is correct
18 Correct 407 ms 4128 KB Output is correct
19 Correct 408 ms 4168 KB Output is correct
20 Correct 332 ms 4168 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 37 ms 3356 KB Output is correct
3 Correct 254 ms 3400 KB Output is correct
4 Correct 442 ms 4396 KB Output is correct
5 Correct 345 ms 3400 KB Output is correct
6 Correct 449 ms 4424 KB Output is correct
7 Correct 453 ms 4424 KB Output is correct
8 Correct 262 ms 3292 KB Output is correct
9 Correct 445 ms 4360 KB Output is correct
10 Execution timed out 3049 ms 5960 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 37 ms 3356 KB Output is correct
3 Correct 254 ms 3400 KB Output is correct
4 Correct 442 ms 4396 KB Output is correct
5 Correct 345 ms 3400 KB Output is correct
6 Correct 449 ms 4424 KB Output is correct
7 Correct 453 ms 4424 KB Output is correct
8 Correct 262 ms 3292 KB Output is correct
9 Correct 445 ms 4360 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 432 ms 3912 KB Output is correct
12 Correct 430 ms 3824 KB Output is correct
13 Correct 405 ms 3912 KB Output is correct
14 Correct 395 ms 3916 KB Output is correct
15 Correct 398 ms 4168 KB Output is correct
16 Correct 51 ms 3400 KB Output is correct
17 Correct 386 ms 4216 KB Output is correct
18 Correct 407 ms 4128 KB Output is correct
19 Correct 408 ms 4168 KB Output is correct
20 Correct 332 ms 4168 KB Output is correct
21 Execution timed out 3049 ms 5960 KB Time limit exceeded
22 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 3070 ms 2420 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 37 ms 3356 KB Output is correct
3 Correct 254 ms 3400 KB Output is correct
4 Correct 442 ms 4396 KB Output is correct
5 Correct 345 ms 3400 KB Output is correct
6 Correct 449 ms 4424 KB Output is correct
7 Correct 453 ms 4424 KB Output is correct
8 Correct 262 ms 3292 KB Output is correct
9 Correct 445 ms 4360 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 432 ms 3912 KB Output is correct
12 Correct 430 ms 3824 KB Output is correct
13 Correct 405 ms 3912 KB Output is correct
14 Correct 395 ms 3916 KB Output is correct
15 Correct 398 ms 4168 KB Output is correct
16 Correct 51 ms 3400 KB Output is correct
17 Correct 386 ms 4216 KB Output is correct
18 Correct 407 ms 4128 KB Output is correct
19 Correct 408 ms 4168 KB Output is correct
20 Correct 332 ms 4168 KB Output is correct
21 Execution timed out 3049 ms 5960 KB Time limit exceeded
22 Halted 0 ms 0 KB -