oj.uz

Submission #799878

# Submission time Handle Problem Language Result Execution time Memory
799878 2023-08-01T07:27:56 Z phoenix Passport (JOI23_passport) C++17
100 / 100
 1633 ms 154996 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;
const int M = (1 << 18);
vector<pair<int, int>> g[3 * M];

void build(int l = 0, int r = M - 1, int v = 1) {
    if(l == r) {
        g[l].push_back({v + M, 0});
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * v);
    build(mid + 1, r, 2 * v + 1);
    g[2 * v + M].push_back({v + M, 0});
    g[2 * v + M + 1].push_back({v + M, 0});
}

void add(int ql, int qr, int u, int l = 0, int r = M - 1, int v = 1) {
    if(qr < l || ql > r) 
        return;
    if(ql <= l && r <= qr) {
        g[v + M].push_back({u, 1});
        return;
    }
    int mid = (l + r) / 2;
    add(ql, qr, u, l, mid, 2 * v);
    add(ql, qr, u, mid + 1, r, 2 * v + 1); 
}

int n;
vector<ll> dijkstra(vector<pair<int, ll>> start) {
    vector<ll> dist(3 * M, INF + 10);
    for(auto [i, d] : start) dist[i] = d;
    set<pair<ll, int>> st;
    for(int i = 0; i < (int)dist.size(); i++) 
        st.insert({dist[i], i});
    while(!st.empty()) {
        int s = st.begin()->second;
        st.erase(st.begin());
        for(auto [to, w] : g[s]) {
            if(dist[to] > dist[s] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[s] + w;
                st.insert({dist[to], to});
            }
        }
    }
    vector<ll> res(n + 1);
    for(int i = 1; i <= n; i++)
        res[i] = dist[i];
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    build();
    cin >> n;
    int l[n + 1], r[n + 1];
    for(int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        add(l[i], r[i], i);
    }
    auto A = dijkstra({{1, 0}});
    auto B = dijkstra({{n, 0}});
    // for(int i = 1; i <= n; i++) 
    //     cout << A[i] << ' ';
    // cout << '\n';
    // for(int i = 1; i <= n; i++) 
    //     cout << B[i] << ' ';
    // cout << '\n';
    vector<pair<int, ll>> C;
    for(int i = 1; i <= n; i++) 
        C.push_back({i, A[i] + B[i] - (1 < i && i < n)});
    auto F = dijkstra(C);
    // for(int i = 1; i <= n; i++) 
    //     cout << F[i] << ' ';
    // cout << '\n';

    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        if(F[x] >= INF) cout << -1 << '\n';
        else cout << F[x] << '\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 98764 KB Output is correct
2 Correct 542 ms 98800 KB Output is correct
3 Correct 578 ms 98796 KB Output is correct
4 Correct 1498 ms 141348 KB Output is correct
5 Correct 1126 ms 121948 KB Output is correct
6 Correct 1008 ms 117936 KB Output is correct
7 Correct 1258 ms 154996 KB Output is correct
8 Correct 790 ms 138748 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 98768 KB Output is correct
2 Correct 611 ms 98764 KB Output is correct
3 Correct 573 ms 98800 KB Output is correct
4 Correct 546 ms 98780 KB Output is correct
5 Correct 559 ms 98824 KB Output is correct
6 Correct 549 ms 98792 KB Output is correct
7 Correct 551 ms 98788 KB Output is correct
8 Correct 556 ms 98764 KB Output is correct
9 Correct 549 ms 98804 KB Output is correct
10 Correct 541 ms 98716 KB Output is correct
11 Correct 552 ms 98872 KB Output is correct
12 Correct 584 ms 98880 KB Output is correct
13 Correct 556 ms 98852 KB Output is correct
14 Correct 562 ms 98888 KB Output is correct
15 Correct 581 ms 98832 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 98768 KB Output is correct
2 Correct 611 ms 98764 KB Output is correct
3 Correct 573 ms 98800 KB Output is correct
4 Correct 546 ms 98780 KB Output is correct
5 Correct 559 ms 98824 KB Output is correct
6 Correct 549 ms 98792 KB Output is correct
7 Correct 551 ms 98788 KB Output is correct
8 Correct 556 ms 98764 KB Output is correct
9 Correct 549 ms 98804 KB Output is correct
10 Correct 541 ms 98716 KB Output is correct
11 Correct 552 ms 98872 KB Output is correct
12 Correct 584 ms 98880 KB Output is correct
13 Correct 556 ms 98852 KB Output is correct
14 Correct 562 ms 98888 KB Output is correct
15 Correct 581 ms 98832 KB Output is correct
16 Correct 567 ms 99084 KB Output is correct
17 Correct 548 ms 99012 KB Output is correct
18 Correct 580 ms 99328 KB Output is correct
19 Correct 589 ms 99216 KB Output is correct
20 Correct 556 ms 99044 KB Output is correct
21 Correct 554 ms 99052 KB Output is correct
22 Correct 577 ms 99316 KB Output is correct
23 Correct 588 ms 99212 KB Output is correct
24 Correct 583 ms 99272 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 98768 KB Output is correct
2 Correct 611 ms 98764 KB Output is correct
3 Correct 573 ms 98800 KB Output is correct
4 Correct 546 ms 98780 KB Output is correct
5 Correct 559 ms 98824 KB Output is correct
6 Correct 549 ms 98792 KB Output is correct
7 Correct 551 ms 98788 KB Output is correct
8 Correct 556 ms 98764 KB Output is correct
9 Correct 549 ms 98804 KB Output is correct
10 Correct 541 ms 98716 KB Output is correct
11 Correct 552 ms 98872 KB Output is correct
12 Correct 584 ms 98880 KB Output is correct
13 Correct 556 ms 98852 KB Output is correct
14 Correct 562 ms 98888 KB Output is correct
15 Correct 581 ms 98832 KB Output is correct
16 Correct 567 ms 99084 KB Output is correct
17 Correct 548 ms 99012 KB Output is correct
18 Correct 580 ms 99328 KB Output is correct
19 Correct 589 ms 99216 KB Output is correct
20 Correct 556 ms 99044 KB Output is correct
21 Correct 554 ms 99052 KB Output is correct
22 Correct 577 ms 99316 KB Output is correct
23 Correct 588 ms 99212 KB Output is correct
24 Correct 583 ms 99272 KB Output is correct
25 Correct 592 ms 98860 KB Output is correct
26 Correct 548 ms 98748 KB Output is correct
27 Correct 567 ms 99204 KB Output is correct
28 Correct 562 ms 99176 KB Output is correct
29 Correct 561 ms 98956 KB Output is correct
30 Correct 589 ms 99064 KB Output is correct
31 Correct 571 ms 99220 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 98764 KB Output is correct
2 Correct 542 ms 98800 KB Output is correct
3 Correct 578 ms 98796 KB Output is correct
4 Correct 1498 ms 141348 KB Output is correct
5 Correct 1126 ms 121948 KB Output is correct
6 Correct 1008 ms 117936 KB Output is correct
7 Correct 1258 ms 154996 KB Output is correct
8 Correct 790 ms 138748 KB Output is correct
9 Correct 570 ms 98768 KB Output is correct
10 Correct 611 ms 98764 KB Output is correct
11 Correct 573 ms 98800 KB Output is correct
12 Correct 546 ms 98780 KB Output is correct
13 Correct 559 ms 98824 KB Output is correct
14 Correct 549 ms 98792 KB Output is correct
15 Correct 551 ms 98788 KB Output is correct
16 Correct 556 ms 98764 KB Output is correct
17 Correct 549 ms 98804 KB Output is correct
18 Correct 541 ms 98716 KB Output is correct
19 Correct 552 ms 98872 KB Output is correct
20 Correct 584 ms 98880 KB Output is correct
21 Correct 556 ms 98852 KB Output is correct
22 Correct 562 ms 98888 KB Output is correct
23 Correct 581 ms 98832 KB Output is correct
24 Correct 567 ms 99084 KB Output is correct
25 Correct 548 ms 99012 KB Output is correct
26 Correct 580 ms 99328 KB Output is correct
27 Correct 589 ms 99216 KB Output is correct
28 Correct 556 ms 99044 KB Output is correct
29 Correct 554 ms 99052 KB Output is correct
30 Correct 577 ms 99316 KB Output is correct
31 Correct 588 ms 99212 KB Output is correct
32 Correct 583 ms 99272 KB Output is correct
33 Correct 592 ms 98860 KB Output is correct
34 Correct 548 ms 98748 KB Output is correct
35 Correct 567 ms 99204 KB Output is correct
36 Correct 562 ms 99176 KB Output is correct
37 Correct 561 ms 98956 KB Output is correct
38 Correct 589 ms 99064 KB Output is correct
39 Correct 571 ms 99220 KB Output is correct
40 Correct 1633 ms 143212 KB Output is correct
41 Correct 1171 ms 124588 KB Output is correct
42 Correct 1300 ms 151648 KB Output is correct
43 Correct 1193 ms 151068 KB Output is correct
44 Correct 956 ms 118000 KB Output is correct
45 Correct 1027 ms 124516 KB Output is correct
46 Correct 815 ms 110924 KB Output is correct
47 Correct 1425 ms 136144 KB Output is correct
48 Correct 1082 ms 135436 KB Output is correct