oj.uz

Submission #793701

# Submission time Handle Problem Language Result Execution time Memory
793701 2023-07-26T05:40:38 Z vjudge1 Passport (JOI23_passport) C++17
100 / 100
 1318 ms 110384 KB 
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;
const int mod = 1e9 + 7;

using namespace std;

int n;
int S;
int a[N], b[N];
vector<pair<int, int>> v[4 * N];

void upd(int x, int l, int r, int tl, int tr, int g)
{
    if (tl > tr) {
        return;
    } else if (l == tl && r == tr) {
        v[x].push_back({g, 1});
        return;
    }
    int m = (l + r) / 2;
    upd(x * 2, l, m, tl, min(m, tr), g);
    upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, g);
}

void solve(vector<int> &d)
{
    set<pair<int, int>> s;
    for (int i = 0; i < d.size(); i++) {
        s.insert({d[i], i});
    }
    while (!s.empty()) {
        int x = s.begin()->se;
        s.erase(s.begin());
        for (auto y: v[x]) {
            if (d[x] + y.se < d[y.fi]) {
                s.erase({d[y.fi], y.fi});
                d[y.fi] = d[x] + y.se;
                s.insert({d[y.fi], y.fi});
            }
        }
    }
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n;

    S = 2;
    while (S < n) {
        S *= 2;
    }

    for (int i = 1; i < S; i++) {
        v[i * 2].push_back({i, 0});
        v[i * 2 + 1].push_back({i, 0});
    }

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];

        a[i]--;
        b[i]--;

        upd(1, 0, S - 1, a[i], b[i], S + i);
    }

    int inf = 1e9;
    vector<int> A(2 * S, inf), B(2 * S, inf), C(2 * S, inf);
    A[S] = 0;
    B[S + n - 1] = 0;

    solve(A);
    solve(B);

    A[S] = B[S + n - 1] = 1;

    for (int i = S; i < 2 * S; i++) {
        C[i] = min(A[i] + B[i] - 1, inf);
    }

    solve(C);

    for (int i = 0; i < 2* S; i++) {
        if (C[i] >= inf) {
            C[i] = -1;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << C[S + x - 1] << "\n";
    }
}

Compilation message

passport.cpp: In function 'void solve(std::vector<int>&)':
passport.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < d.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 12 ms 19052 KB Output is correct
4 Correct 1004 ms 95800 KB Output is correct
5 Correct 636 ms 76004 KB Output is correct
6 Correct 474 ms 72680 KB Output is correct
7 Correct 539 ms 84684 KB Output is correct
8 Correct 407 ms 86292 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 12 ms 19028 KB Output is correct
9 Correct 12 ms 19080 KB Output is correct
10 Correct 10 ms 19148 KB Output is correct
11 Correct 13 ms 19220 KB Output is correct
12 Correct 11 ms 19192 KB Output is correct
13 Correct 11 ms 19156 KB Output is correct
14 Correct 10 ms 19132 KB Output is correct
15 Correct 13 ms 19188 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 12 ms 19028 KB Output is correct
9 Correct 12 ms 19080 KB Output is correct
10 Correct 10 ms 19148 KB Output is correct
11 Correct 13 ms 19220 KB Output is correct
12 Correct 11 ms 19192 KB Output is correct
13 Correct 11 ms 19156 KB Output is correct
14 Correct 10 ms 19132 KB Output is correct
15 Correct 13 ms 19188 KB Output is correct
16 Correct 19 ms 20052 KB Output is correct
17 Correct 16 ms 19924 KB Output is correct
18 Correct 16 ms 20180 KB Output is correct
19 Correct 16 ms 20180 KB Output is correct
20 Correct 14 ms 19908 KB Output is correct
21 Correct 15 ms 19908 KB Output is correct
22 Correct 15 ms 20032 KB Output is correct
23 Correct 15 ms 20040 KB Output is correct
24 Correct 14 ms 20040 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 10 ms 19020 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 12 ms 19028 KB Output is correct
9 Correct 12 ms 19080 KB Output is correct
10 Correct 10 ms 19148 KB Output is correct
11 Correct 13 ms 19220 KB Output is correct
12 Correct 11 ms 19192 KB Output is correct
13 Correct 11 ms 19156 KB Output is correct
14 Correct 10 ms 19132 KB Output is correct
15 Correct 13 ms 19188 KB Output is correct
16 Correct 19 ms 20052 KB Output is correct
17 Correct 16 ms 19924 KB Output is correct
18 Correct 16 ms 20180 KB Output is correct
19 Correct 16 ms 20180 KB Output is correct
20 Correct 14 ms 19908 KB Output is correct
21 Correct 15 ms 19908 KB Output is correct
22 Correct 15 ms 20032 KB Output is correct
23 Correct 15 ms 20040 KB Output is correct
24 Correct 14 ms 20040 KB Output is correct
25 Correct 10 ms 19028 KB Output is correct
26 Correct 9 ms 19028 KB Output is correct
27 Correct 19 ms 20044 KB Output is correct
28 Correct 19 ms 19924 KB Output is correct
29 Correct 17 ms 19912 KB Output is correct
30 Correct 17 ms 19944 KB Output is correct
31 Correct 18 ms 20036 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 12 ms 19052 KB Output is correct
4 Correct 1004 ms 95800 KB Output is correct
5 Correct 636 ms 76004 KB Output is correct
6 Correct 474 ms 72680 KB Output is correct
7 Correct 539 ms 84684 KB Output is correct
8 Correct 407 ms 86292 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 10 ms 19020 KB Output is correct
12 Correct 9 ms 19028 KB Output is correct
13 Correct 10 ms 19028 KB Output is correct
14 Correct 10 ms 19028 KB Output is correct
15 Correct 9 ms 19028 KB Output is correct
16 Correct 12 ms 19028 KB Output is correct
17 Correct 12 ms 19080 KB Output is correct
18 Correct 10 ms 19148 KB Output is correct
19 Correct 13 ms 19220 KB Output is correct
20 Correct 11 ms 19192 KB Output is correct
21 Correct 11 ms 19156 KB Output is correct
22 Correct 10 ms 19132 KB Output is correct
23 Correct 13 ms 19188 KB Output is correct
24 Correct 19 ms 20052 KB Output is correct
25 Correct 16 ms 19924 KB Output is correct
26 Correct 16 ms 20180 KB Output is correct
27 Correct 16 ms 20180 KB Output is correct
28 Correct 14 ms 19908 KB Output is correct
29 Correct 15 ms 19908 KB Output is correct
30 Correct 15 ms 20032 KB Output is correct
31 Correct 15 ms 20040 KB Output is correct
32 Correct 14 ms 20040 KB Output is correct
33 Correct 10 ms 19028 KB Output is correct
34 Correct 9 ms 19028 KB Output is correct
35 Correct 19 ms 20044 KB Output is correct
36 Correct 19 ms 19924 KB Output is correct
37 Correct 17 ms 19912 KB Output is correct
38 Correct 17 ms 19944 KB Output is correct
39 Correct 18 ms 20036 KB Output is correct
40 Correct 1318 ms 100040 KB Output is correct
41 Correct 864 ms 81076 KB Output is correct
42 Correct 994 ms 110384 KB Output is correct
43 Correct 988 ms 109768 KB Output is correct
44 Correct 777 ms 77696 KB Output is correct
45 Correct 788 ms 81640 KB Output is correct
46 Correct 369 ms 48528 KB Output is correct
47 Correct 972 ms 88092 KB Output is correct
48 Correct 960 ms 92636 KB Output is correct