oj.uz

Submission #1108681

# Submission time Handle Problem Language Result Execution time Memory
1108681 2024-11-04T18:49:12 Z vladilius Escape Route 2 (JOI24_escape2) C++17
6 / 100
 3000 ms 6216 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;
    }
    
    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 38 ms 3448 KB Output is correct
3 Correct 248 ms 3400 KB Output is correct
4 Correct 443 ms 4360 KB Output is correct
5 Correct 347 ms 3400 KB Output is correct
6 Correct 457 ms 4348 KB Output is correct
7 Correct 443 ms 4344 KB Output is correct
8 Correct 250 ms 3400 KB Output is correct
9 Correct 445 ms 4436 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 38 ms 3448 KB Output is correct
3 Correct 248 ms 3400 KB Output is correct
4 Correct 443 ms 4360 KB Output is correct
5 Correct 347 ms 3400 KB Output is correct
6 Correct 457 ms 4348 KB Output is correct
7 Correct 443 ms 4344 KB Output is correct
8 Correct 250 ms 3400 KB Output is correct
9 Correct 445 ms 4436 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 432 ms 3928 KB Output is correct
12 Correct 433 ms 3756 KB Output is correct
13 Correct 398 ms 3784 KB Output is correct
14 Correct 395 ms 3800 KB Output is correct
15 Correct 409 ms 4080 KB Output is correct
16 Correct 42 ms 3288 KB Output is correct
17 Correct 381 ms 4284 KB Output is correct
18 Correct 400 ms 4112 KB Output is correct
19 Correct 455 ms 4168 KB Output is correct
20 Incorrect 439 ms 4272 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 38 ms 3448 KB Output is correct
3 Correct 248 ms 3400 KB Output is correct
4 Correct 443 ms 4360 KB Output is correct
5 Correct 347 ms 3400 KB Output is correct
6 Correct 457 ms 4348 KB Output is correct
7 Correct 443 ms 4344 KB Output is correct
8 Correct 250 ms 3400 KB Output is correct
9 Correct 445 ms 4436 KB Output is correct
10 Execution timed out 3042 ms 6216 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 38 ms 3448 KB Output is correct
3 Correct 248 ms 3400 KB Output is correct
4 Correct 443 ms 4360 KB Output is correct
5 Correct 347 ms 3400 KB Output is correct
6 Correct 457 ms 4348 KB Output is correct
7 Correct 443 ms 4344 KB Output is correct
8 Correct 250 ms 3400 KB Output is correct
9 Correct 445 ms 4436 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 432 ms 3928 KB Output is correct
12 Correct 433 ms 3756 KB Output is correct
13 Correct 398 ms 3784 KB Output is correct
14 Correct 395 ms 3800 KB Output is correct
15 Correct 409 ms 4080 KB Output is correct
16 Correct 42 ms 3288 KB Output is correct
17 Correct 381 ms 4284 KB Output is correct
18 Correct 400 ms 4112 KB Output is correct
19 Correct 455 ms 4168 KB Output is correct
20 Incorrect 439 ms 4272 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 3086 ms 2464 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 38 ms 3448 KB Output is correct
3 Correct 248 ms 3400 KB Output is correct
4 Correct 443 ms 4360 KB Output is correct
5 Correct 347 ms 3400 KB Output is correct
6 Correct 457 ms 4348 KB Output is correct
7 Correct 443 ms 4344 KB Output is correct
8 Correct 250 ms 3400 KB Output is correct
9 Correct 445 ms 4436 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 432 ms 3928 KB Output is correct
12 Correct 433 ms 3756 KB Output is correct
13 Correct 398 ms 3784 KB Output is correct
14 Correct 395 ms 3800 KB Output is correct
15 Correct 409 ms 4080 KB Output is correct
16 Correct 42 ms 3288 KB Output is correct
17 Correct 381 ms 4284 KB Output is correct
18 Correct 400 ms 4112 KB Output is correct
19 Correct 455 ms 4168 KB Output is correct
20 Incorrect 439 ms 4272 KB Output isn't correct
21 Halted 0 ms 0 KB -