Submission #1261228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261228		SzymonKrzywda	Passport (JOI23_passport)	C++20	54 / 100	2095 ms	79344 KiB

passport

#pragma GCC optimize("O3,unroll-loops,Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int base = 1 << 18;
const int MAXN = 2 * base;
const int INF  = 1e9;

int wygrana = 0;
int n, a, b;
vector<pii> prz;
vector<pii> graf2[MAXN];

int dist[MAXN], vis[MAXN], timer = 0;

vector<int> bfs01(int start) {
    timer++;
    deque<int> dq;
    for (int i = 0; i < MAXN; i++) dist[i] = INF;
    
    if (start != wygrana) {
        for (int i = 0; i < n; i++) {
            if (prz[i].first <= start - base && prz[i].second >= start - base) {
                dist[i + base] = 0;
                vis[i + base] = timer;
                dq.push_back(i + base);
            }
        }
    }
    dist[start] = 0;
    vis[start] = timer;
    dq.push_back(start);

    while (!dq.empty()) {
        int v = dq.front(); dq.pop_front();
        for (auto &[s,w] : graf2[v]) {
            if (vis[s] != timer || dist[s] > dist[v] + w) {
                dist[s] = dist[v] + w;
                vis[s] = timer;
                if (w == 0) dq.push_front(s);
                else dq.push_back(s);
            }
        }
    }
    return vector<int>(dist, dist+MAXN);
}

void build(int v){
    if (v >= base) return;
    graf2[v*2].push_back({v,0});
    graf2[v*2+1].push_back({v,0});
    build(v*2);
    build(v*2+1);
}

void dodaj(int idx, int a, int b){
    a += base - 1; b += base + 1; idx += base;
    while (a/2 != b/2){
        if (!(a&1)) graf2[a+1].push_back({idx,1});
        if (b&1)    graf2[b-1].push_back({idx,1});
        a/=2; b/=2;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    build(1);

    for (int i=0;i<n;i++){
        cin >> a >> b;
        a--; b--;
        dodaj(i,a,b);
        prz.push_back({a,b});
    }

    vector<int> odl1 = bfs01(base);
    vector<int> odln = bfs01(base+n-1);

    for (int i = base; i < base+n; i++)
        graf2[wygrana].push_back({i, odl1[i] + odln[i]});

    vector<int> odp = bfs01(wygrana);

    int q,val;
    cin >> q;
    while(q--){
        cin >> val;
        int res = odp[base+val-1];
        cout << (res>=INF ? -1 : res+1) << '\n';
    }
}

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