Submission #1261149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261149		niepamietamhasla	Passport (JOI23_passport)	C++20	100 / 100	419 ms	42840 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>

const int MAXN = 2e5 + 5;

pii range[MAXN];
int used[MAXN];

int minod1[MAXN];
int minodn[MAXN];
int ans[MAXN];

const int base = 1 << 18;
vector<int> drzew[base << 1];

void dodaj(int w, int a, int b, int akt_a, int akt_b, int ind){
    if(a <= akt_a and akt_b <= b){
        drzew[w].push_back(ind);
        return;
    }
    if(akt_a > b or akt_b < a) return;
    int mid = (akt_a + akt_b) / 2;
    dodaj(2 * w, a, b, akt_a, mid, ind);
    dodaj(2 * w + 1, a, b, mid + 1, akt_b, ind);
    return;
}

void preptree(int n){
    for(int i = 1; i < 2 * base; ++i){
        drzew[i].clear();
    }
    for(int i = 1; i <= n; ++i){
        used[i] = 0;
        dodaj(1, range[i].first, range[i].second, 1, base, i);
    }
    return;
}

struct comp{
    bool operator()(const pii &p1, const pii &p2){
        if(p1.second != p2.second) return p1.second > p2.second;
        return false;       
    }
};

queue<pii> que;
priority_queue<pii, vector<pii>, comp> pq;

void dodajnad(int w, int koszt, int typ){
    w += base - 1;
    while(w != 0){
        for(auto u : drzew[w]){
            if(used[u] == 1) continue;
            used[u] = 1;
            if(typ == 1) que.push({u, koszt + 1});
            else pq.push((pii){u, koszt + 1});
        }
        drzew[w].clear();
        w /= 2;
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a, b;
    for(int i = 1; i <= n; ++i){
        cin >> a >> b;
        range[i] = {a, b};
        minod1[i] = minodn[i] = 1e9;
        ans[i] = 1e9;
    }
    preptree(n);
    que.push({1, 0});
    while(!que.empty()){
        auto e = que.front();
        que.pop();
        if(minod1[e.first] != 1e9) continue;
        minod1[e.first] = e.second;
        dodajnad(e.first, e.second, 1);
    }
    preptree(n);
    que.push({n, 0});
    while(!que.empty()){
        auto e = que.front();
        que.pop();
        if(minodn[e.first] != 1e9) continue;
        minodn[e.first] = e.second;
        dodajnad(e.first, e.second, 1);
    }

    preptree(n);
    for(int i = 1; i <= n; ++i){
        pq.push((pii){i, minod1[i] + minodn[i] - 1 * (i != 1 and i != n ? 1 : 0)});
    }

    while(!pq.empty()){
        auto e = pq.top();
        pq.pop();
        if(ans[e.first] != 1e9) continue;
        ans[e.first] = e.second;
        dodajnad(e.first, e.second, 2);
    }
    


    int q;
    cin >> q;
    for(int i = 0; i < q; ++i){
        cin >> a;
        if(ans[a] < 1e9) cout << ans[a] << "\n";
        else cout << -1 << "\n";
    }
    return 0;
}

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