Submission #1261203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261203		M_W_13	Passport (JOI23_passport)	C++20	100 / 100	405 ms	17724 KiB

passport

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 19;
const int INF = 1e9;
bool odw[MAXN][2];
bool od[MAXN];
int pom[MAXN][2];
int ans[MAXN];
pair<int, int> T[MAXN];
pair<int, int> maks[2 * MAXN];
pair<int, int> mini[2 * MAXN];

int N = 1;

void updmaks(int v, int x) {
    v += N;
    maks[v] = {x, v - N};
    v /= 2;
    while (v > 0) {
        maks[v] = max(maks[2 * v], maks[2 * v + 1]);
        v /= 2;
    }
}

void updmini(int v, int x) {
    v += N;
    mini[v] = {x, v - N};
    v /= 2;
    while (v > 0) {
        mini[v] = min(mini[2 * v], mini[2 * v + 1]);
        v /= 2;
    }
}

pair<int, int> querymaks(int l, int r) {
    l += N;
    r += N;
    pair<int, int> ans = {-1, -1};
    while (l < r) {
        if (l % 2 == 1) {
            ans = max(ans, maks[l]);
            l++;
        }
        if (r % 2 == 0) {
            ans = max(ans, maks[r]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        ans = max(ans, maks[l]);
    }
    return ans;
}

pair<int, int> querymini(int l, int r) {
    l += N;
    r += N;
    pair<int, int> ans = {INF, -1};
    while (l < r) {
        if (l % 2 == 1) {
            ans = min(ans, mini[l]);
            l++;
        }
        if (r % 2 == 0) {
            ans = min(ans, mini[r]);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        ans = min(ans, mini[l]);
    }
    return ans;
}

void bfs(int n, int v, int c) {
    rep(i, n) {
        pom[i][c] = INF;
    }
    queue<pair<int, int>> q;
    q.push({v, 0});
    odw[v][c] = true;
    while (!q.empty()) {
        // cout << "XD2" << endl;
        pair<int, int> p = q.front();
        q.pop();
        v = p.st;
        int d = p.nd;
        pom[v][c] = d;
        if (d == 0) {
            pom[v][c] = 1;
        }
        if (v > 0) {
            // if (v == n - 1 && c == 1) {
            //     cout << querymaks(0, v - 1).st << " " << querymaks(0, v - 1).nd << '\n';
            // }
            while (querymaks(0, v - 1).st >= v) {
                pair<int, int> p2 = querymaks(0, v - 1);
                int w = p2.nd;
                updmaks(w, -1);
                updmini(w, INF);
                if (!odw[w][c]) {
                    odw[w][c] = true;
                    q.push({w, d + 1});
                }
            }
        }
        if (v < n - 1) {
            while (querymini(v + 1, n - 1).st <= v) {
                pair<int, int> p2 = querymini(v + 1, n - 1);
                int w = p2.nd;
                updmaks(w, -1);
                updmini(w, INF);
                if (!odw[w][c]) {
                    odw[w][c] = true;
                    q.push({w, d + 1});
                }
            }
        }
        // cout << "SK2" << endl;
    }
}

class compare {
    public:
        bool operator() (pair<int, int> a, pair<int, int> b) {
            return a.st > b.st;
        }
};

void dijkstra(int n) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
    rep(i, n) {
        ans[i] = INF;
        // cout << (pom[i][0] + pom[i][1] - 1) << " " << i << '\n';
        pq.push({pom[i][0] + pom[i][1] - 1, i});
    }
    while (!pq.empty()) {
        // cout << "XD" << endl;
        pair<int, int> p = pq.top();
        pq.pop();
        int v = p.nd;
        int d = p.st;
        // cout << "v = " << v << endl;
        // cout << "PR" << endl;
        if (od[v]) continue;
        // cout << "HUH" << endl;
        // cout << "v = " << v << " d = " << d << endl;
        od[v] = true;
        ans[v] = d;
        if (v > 0) {
            while (querymaks(0, v - 1).st >= v) {
                pair<int, int> p2 = querymaks(0, v - 1);
                int w = p2.nd;
                updmaks(w, -1);
                updmini(w, INF);
                if (!od[w]) {
                    pq.push({d + 1, w});
                }
            }
        }
        if (v < n - 1) {
            while (querymini(v + 1, n - 1).st <= v) {
                pair<int, int> p2 = querymini(v + 1, n - 1);
                int w = p2.nd;
                updmaks(w, -1);
                updmini(w, INF);
                if (!od[w]) {
                    pq.push({d + 1, w});
                }
            }
        }
        // cout << "SK" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    while (N < n) N *= 2;
    rep(i, 2 * N) {
        maks[i] = {-1, -1};
        mini[i] = {INF, -1};
    }
    rep(i, n) {
        cin >> T[i].st >> T[i].nd;
        T[i].st--;
        T[i].nd--;
        updmaks(i, T[i].nd);
        updmini(i, T[i].st);
    }
    bfs(n, 0, 0);
    rep(i, n) {
        updmaks(i, T[i].nd);
        updmini(i, T[i].st);
    }
    bfs(n, n - 1, 1);
    rep(i, n) {
        // cout << pom[i][0] << " " << pom[i][1] << '\n';
        updmaks(i, T[i].nd);
        updmini(i, T[i].st);
    }
    dijkstra(n);
    // cout << "WTH" << endl;
    int q;
    cin >> q;
    // cout << "HAHA" << endl;
    rep(i, q) {
        int x;
        cin >> x;
        x--;
        if (ans[x] >= INF) {
            cout << -1 << '\n';
            continue;
        }
        cout << ans[x] << '\n';
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46