Submission #1049136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049136		Andrey	Passport (JOI23_passport)	C++14	48 / 100	323 ms	229708 KiB

passport

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> haha(200001);
vector<pair<int,int>> sm(1000001);
vector<pair<int,int>> big(1000001);
vector<int> seg[1000001];
vector<int> dp1(100001,1000000);
vector<int> dp2(100001,1000000);
vector<int> dp(100001,1000000);
vector<int> wow[1000001];

void build(int l, int r, int x) {
    if(l == r) {
        big[x] = {haha[l].second,l};
        sm[x] = {haha[l].first,l};
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    big[x] = max(big[x*2],big[x*2+1]);
    sm[x] = min(sm[x*2],sm[x*2+1]);
}

pair<int,int> calc(int l, int r, int ql, int qr, int x, bool yeah) {
    if(ql == l && qr == r) {
        if(yeah) {
            return sm[x];
        }
        else {
            return big[x];
        }
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        return calc(l,mid,ql,qr,x*2,yeah);
    }
    else if(ql > mid) {
        return calc(mid+1,r,ql,qr,x*2+1,yeah);
    }
    else {
        pair<int,int> a = calc(l,mid,ql,mid,x*2,yeah),b = calc(mid+1,r,mid+1,qr,x*2+1,yeah);
        if(yeah) {
            return min(a,b);
        }
        else {
            return max(a,b);
        }
    }
}

void dfs(int a, bool yeah, int d) {
    if(yeah) {
        dp1[a] = d;
    }
    else {
        dp2[a] = d;
    }
    for(int v: wow[a]) {
        dfs(v,yeah,d+1);
    }
}

void dude(int l, int r, int ql, int qr, int x, int c) {
    if(ql == l && qr == r) {
        seg[x].push_back(c);
        return;
    }
    int mid = (l+r)/2;
    if(qr <= mid) {
        dude(l,mid,ql,qr,x*2,c);
    }
    else if(ql > mid) {
        dude(mid+1,r,ql,qr,x*2+1,c);
    }
    else {
        dude(l,mid,ql,mid,x*2,c);
        dude(mid+1,r,mid+1,qr,x*2+1,c);
    }
}

vector<int> troll[1000001];

void banana(int l, int r, int x, int p, int br) {
    for(int c: seg[x]) {
        if(dp[c] > br) {
            dp[c] = br;
            troll[br].push_back(c);
        }
    }
    seg[x].clear();
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    if(p <= mid) {
        banana(l,mid,x*2,p,br);
    }
    else {
        banana(mid+1,r,x*2+1,p,br);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,l,r;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> l >> r;
        haha[i] = {l,r};
    }
    build(1,n,1);
    for(int i = 1; i <= n; i++) {
        pair<int,int> a = calc(1,n,haha[i].first,haha[i].second,1,1);
        if(a.first < haha[i].first) {
            wow[a.second].push_back(i);
        }
        else if(a.first == 1) {
            dp1[i] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(dp1[i] == 0) {
            dfs(i,1,0);
        }
    }
    for(int i = 1; i <= n; i++) {
        wow[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        pair<int,int> a = calc(1,n,haha[i].first,haha[i].second,1,0);
        if(a.first > haha[i].second) {
            wow[a.second].push_back(i);
        }
        else if(a.second == n) {
            dp2[i] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(dp2[i] == 0) {
            dfs(i,0,0);
        }
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = dp1[i]+dp2[i]+1;
        if(dp[i] <= n) {
            troll[dp[i]].push_back(i);
        }
    }
    for(int i = 1; i <= n; i++) {
        dude(1,n,haha[i].first,haha[i].second,1,i);
    }
    for(int i = 0; i <= n; i++) {
        for(int v: troll[i]) {
            if(dp[v] == i) {
                banana(1,n,1,v,dp[v]+1);
            }
        }
    }
    int q,x;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> x;
        if(dp[x] <= n) {
            cout << dp[x] << "\n";
        }
        else {
            cout << -1 << "\n";
        }
    }
    return 0;
}

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