Submission #963026

#	Time	Username	Problem	Language	Result	Execution time	Memory
963026		RaresFelix	Passport (JOI23_passport)	C++17	100 / 100	1103 ms	79384 KiB

passport

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

const int INF = 1e9;

struct AIB {
    ///maxime pe sufix
    int n;
    vi V;

    AIB(int N) : n(N + 1), V(N + 1, INF) {}

    void insert(int p, int v) {
        p = n - p - 1;
        while(p < n) {
            V[p] = min(V[p], v);
            p += p & -p;
        }
    }

    int query(int p) {
        int re = INF;
        p = n - p - 1;
        while(p) {
            re = min(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vi L(n), R(n);
    for(int i = 0; i < n; ++i) {
        cin >> L[i] >> R[i];
        --L[i]; --R[i];
    }
    vi CS(n), CD(n);

    int n0 = n;
    while(n & (n - 1)) n += n & -n;

    vector<vector<ii> > G(2 * n);
    
    function<void(int, int, int, int, int, int, int)> add_edge_2 = 
        [&](int l, int r, int v, int w, int u, int s, int d) {
        ///adauga muchie de la segmentul (l, r) la v
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            G[u].push_back({v, w});
            return;
        }
        add_edge_2(l, r, v, w, u << 1, s, (s + d) >> 1);
        add_edge_2(l, r, v, w, u << 1 | 1, ((s + d) >> 1) + 1, d);
    };
    auto add_edge = [&](int l, int r, int v, int w) 
        { add_edge_2(l, r, v, w, 1, 0, n - 1); };

    auto resetG = [&]() {
        for(int i = 0; i < 2 * n; ++i) G[i].clear();

        for(int i = 2; i < 2 * n; ++i)
            G[i].push_back({i / 2, 0});

        for(int i = 0; i < n0; ++i)
            add_edge(L[i], R[i], i + n, 1);
    };

    vi Dist(2 * n);
    auto Dijkstra = [&](int s) {
        for(int i = 0; i < 2 * n; ++i) Dist[i] = INF;
        Dist[s] = 0;
        priority_queue<ii> PQ;
        PQ.push({s, 0});
        while(!PQ.empty()) {
            auto [d, u] = PQ.top();
            PQ.pop();
            if(Dist[u] != -d) continue;
            for(auto [it, w] : G[u]) {
                if(Dist[it] > Dist[u] + w) {
                    Dist[it] = Dist[u] + w;
                    PQ.push({-Dist[it], it});
                }
            }
        }
    };

    resetG();
    for(int i = 0; i < n0; ++i)
        if(L[i] == 0) G[0].push_back({i + n, 0});
    Dijkstra(0);
    for(int i = 0; i < n0; ++i) CS[i] = Dist[i + n];

    resetG();
    for(int i = 0; i < n0; ++i)
        if(R[i] == n0 - 1) G[0].push_back({i + n, 0});
    Dijkstra(0);
    for(int i = 0; i < n0; ++i) CD[i] = Dist[i + n];

    resetG();
    for(int i = 0; i < n0; ++i)
        G[0].push_back({i + n, CS[i] + CD[i]});
    Dijkstra(0);
    int q;
    cin >> q;
    for(int i = 0; i < q; ++i) {
        int u;
        cin >> u;
        --u;
        int re = Dist[u + n] + 1;
        if(re >= INF) re = -1;
        cout << re << "\n";
    }
    return 0;
}

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