Submission #793670

#	Time	Username	Problem	Language	Result	Execution time	Memory
793670		vjudge1	Passport (JOI23_passport)	C++17	6 / 100	1056 ms	98264 KiB

passport

#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);

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

    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 (stderr)

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 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46