Submission #747852

#	Time	Username	Problem	Language	Result	Execution time	Memory
747852		stevancv	Passport (JOI23_passport)	C++14	100 / 100	1301 ms	96344 KiB

passport

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int inf = 1e9;
int n, l[N], r[N];
int dl[5 * N], dr[5 * N], dist[5 * N], gde[N];
void Init(int node, int l, int r) {
    if (l == r) {gde[l] = node; return;}
    int mid = l + r >> 1;
    Init(2 * node, l, mid);
    Init(2 * node + 1, mid + 1, r);
}
vector<int> g[5 * N];
void Add(int node, int l, int r, int ql, int qr, int i) {
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
        g[i].push_back(n + node);
        g[n + node].push_back(i);
        return;
    }
    int mid = l + r >> 1;
    Add(2 * node, l, mid, ql, qr, i);
    Add(2 * node + 1, mid + 1, r, ql, qr, i);
}
void Bfs(int* d) {
    set<pair<int, int>> st;
    for (int i = 1; i <= n; i++) st.insert({d[i], i});
    while (!st.empty()) {
        auto it = st.begin();
        int s = it->second;
        st.erase(it);
        if (s <= n) {
            for (int u = gde[s]; u >= 1; u /= 2) {
                if (d[u + n] > d[s]) {
                    if (st.find({d[u + n], u + n}) != st.end()) st.erase({d[u + n], u + n});
                    d[u + n] = d[s];
                    st.insert({d[u + n], u + n});
                }
            }
            continue;
        }
        for (int u : g[s]) {
            if (d[u] > d[s] + 1) {
                if (st.find({d[u], u}) != st.end()) st.erase({d[u], u});
                d[u] = d[s] + 1;
                st.insert({d[u], u});
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    Init(1, 1, n);
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        Add(1, 1, n, l[i], r[i], i);
    }
    for (int i = 1; i <= 5 * n; i++) dl[i] = dr[i] = dist[i] = inf;
    dl[1] = 0; dr[n] = 0;
    Bfs(dl); Bfs(dr);
    dl[1] = 1; dr[n] = 1;
    for (int i = 1; i <= n; i++) dist[i] = dl[i] + dr[i];
    Bfs(dist);
    for (int i = 1; i <= n; i++) {
        if (dist[i] >= inf) dist[i] = -1;
        else dist[i] -= 1;
    }
    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << dist[x] << en;
    }
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void Init(int, int, int)':
passport.cpp:15:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int mid = l + r >> 1;
      |               ~~^~~
passport.cpp: In function 'void Add(int, int, int, int, int, int)':
passport.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int mid = l + r >> 1;
      |               ~~^~~

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