Submission #1308222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308222		viobow	Passport (JOI23_passport)	C++17	100 / 100	941 ms	148052 KiB

passport

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define re exit(0);
#define FOR(i, a, b)   for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b)  for(int i = (a), _b = (b); i >= _b; i--)
#define LOOP(a)        for(int i = 0, _a = (a); i < _a; i++)
#define left id<<1
#define right id<<1|1
#define _lower(v, x) lower_bound(v.begin(), v.end(), x) - v.begin() + 1

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

template<typename T> void chkmin(T &x, T y) {if (y < x) x = y;}
template<typename T> void chkmax(T &x, T y) {if (y > x) x = y;}

const int mod = 1e9 + 7;
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int _pow(int a, int b) {
   int ans = 1;
   while (b) {
   if (b % 2 == 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b /= 2;
   }
   return ans;
}

//--------------------------------------------------------------------------------------------------------------------------------------

const int INF = 1e15 + 7;
const int maxn = 2e5;

struct state {
    int pos, cost;
    bool operator< (const state &other) const {
        return cost > other.cost;
    }
};

int L[maxn + 5], R[maxn + 5], X[maxn + 5];
vii adjList[4 * maxn + 5];
int virtual_id[maxn + 5]; bool isLeaf[4 * maxn + 5];
int n, numQuery;

void build_virtual_id(int id, int l, int r) {
    if (l == r) {
        virtual_id[l] = id;
        isLeaf[id] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build_virtual_id(left, l, mid);
    build_virtual_id(right, mid + 1, r);
    adjList[left].pb({id, 0});
    adjList[right].pb({id, 0});
}

void make_edge(int id, int l, int r, int u, int v, int source) {
    if (r < u || l > v) return;
    if (u <= l && r <= v) {
        adjList[id].pb({source, 1});
        return;
    }
    int mid = (l + r) >> 1;
    make_edge(left, l, mid, u, v, source);
    make_edge(right, mid + 1, r, u, v, source);
}

vector<int> uwu(vector<int> init_dist) {
    vector<int> d = init_dist;
    priority_queue<state> Q;

    for (int i = 1; i < (int)d.size(); i++) {
        if (d[i] != INF) Q.push({i, d[i]});
    }

    while (Q.size()) {
        auto top = Q.top(); Q.pop();
        int u = top.pos;
        if (d[u] < top.cost) continue;

        for (auto [v, w] : adjList[u]) {
            if (d[v] > d[u] + w) {
                Q.push({v, d[v] = d[u] + w});
            }
        }
    }

    return d;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //#define name "mooo"
    //if (fopen(name".inp", "r")) {
    //    freopen(name".inp", "r", stdin);
    //    freopen(name".out", "w", stdout);
    //}

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> L[i] >> R[i];

    cin >> numQuery;
    for (int i = 1; i <= numQuery; i++)
        cin >> X[i];

    build_virtual_id(1, 1, n);
    for (int i = 1; i <= n; i++)
        make_edge(1, 1, n, L[i], R[i], virtual_id[i]);

    vector<int> init_dist(4 * maxn + 5, INF);
    init_dist[virtual_id[1]] = 0;
    vector<int> d1 = uwu(init_dist);
    d1[virtual_id[1]] = 1;

    init_dist.assign(4 * maxn + 5, INF);
    init_dist[virtual_id[n]] = 0;
    vector<int> dn = uwu(init_dist);
    dn[virtual_id[n]] = 1;

    init_dist.assign(4 * maxn + 5, INF);
    for (int i = 1; i <= n; i++) {
        int u = virtual_id[i];
        if (d1[u] == INF || dn[u] == INF) init_dist[u] = INF;
        else init_dist[u] = d1[u] + dn[u] - 1;
    }
    vector<int> d = uwu(init_dist);

    for (int i = 1; i <= numQuery; i++) {
        int res = d[virtual_id[X[i]]];
        if (res == INF) res = -1;
        cout << res << '\n';
    }

    return 0;
}

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