Submission #757730

#	Time	Username	Problem	Language	Result	Execution time	Memory
757730		happypotato	Passport (JOI23_passport)	C++17	46 / 100	125 ms	57272 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
const int mxN = 2e5 + 1;
pii range[mxN];
int ans[mxN];
int n;
void init() {
    // init
    for (int i = 1; i < mxN; i++) ans[i] = -1;
}
void st5() {

}
void st4() {

}
int st3dp[2501][2501];
int st3(int &tar) {
    if (range[tar].ff == 1 && range[tar].ss == n) {
        return 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            st3dp[i][j] = 1e9;
        }
    }
    queue<pii> q;
    q.push({tar, tar});
    st3dp[tar][tar] = 1;
    int nl, nr;
    while (!q.empty()) {
        pii cur = q.front(); q.pop();
        for (int i = range[cur.ff].ff; i < cur.ff; i++) {
            if (range[cur.ff].ff <= range[i].ff && range[i].ss <= range[cur.ss].ss) continue;
            nl = (range[cur.ff].ff <= range[i].ff ? cur.ff : i);
            nr = (range[i].ss <= range[cur.ss].ss ? cur.ss : i);
            if (st3dp[nl][nr] > st3dp[cur.ff][cur.ss] + 1) {
                st3dp[nl][nr] = st3dp[cur.ff][cur.ss] + 1;
                if (range[nl].ff == 1 && range[nr].ss == n) {
                    return st3dp[nl][nr];
                }
                q.push({nl, nr});
            }
        }
        for (int i = cur.ss + 1; i <= range[cur.ss].ss; i++) {
            if (range[cur.ff].ff <= range[i].ff && range[i].ss <= range[cur.ss].ss) continue;
            nl = (range[cur.ff].ff <= range[i].ff ? cur.ff : i);
            nr = (range[i].ss <= range[cur.ss].ss ? cur.ss : i);
            if (st3dp[nl][nr] > st3dp[cur.ff][cur.ss] + 1) {
                st3dp[nl][nr] = st3dp[cur.ff][cur.ss] + 1;
                if (range[nl].ff == 1 && range[nr].ss == n) {
                    return st3dp[nl][nr];
                }
                q.push({nl, nr});
            }
        }
    }
    return -1;
}
int st2dp[301][301];
void st2recur(int l, int r, int val) {
    st2dp[l][r] = val;
    int nl, nr;
    for (int i = l; i <= r; i++) {
        nl = min(l, range[i].ff);
        nr = max(r, range[i].ss);
        if (st2dp[nl][nr] > val + 1) {
            st2recur(nl, nr, val + 1);
        }
    }
}
int st2(int &tar) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            st2dp[i][j] = 1e9;
        }
    }
    st2recur(range[tar].ff, range[tar].ss, 1);
    return (st2dp[1][n] == 1e9 ? -1 : st2dp[1][n]);
}
int st1() {
    int ans = 1;
    int cur = range[1].ss;
    int ptr = 1;
    while (cur < n) {
        int maxi = cur;
        while (ptr <= cur) {
            maxi = max(maxi, range[ptr].ss);
            ptr++;
        }
        if (maxi == cur) return -1;
        ans++;
        cur = maxi;
    }
    return ans;
}
void solve() {
    // solve
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> range[i].ff >> range[i].ss;
    }
    int q;
    cin >> q;
    if (q == 1) {
        int cur;
        cin >> cur;
        if (cur == 1) {
            cout << st1() << endl;
        } else if (n <= 300) {
            cout << st2(cur) << endl;
        } else if (n <= 2500) {
            cout << st3(cur) << endl;
        } else {
            st5();
            cout << ans[cur] << endl;
        }
        return;
    }
    if (n <= 2500) {
        st4();
    } else {
        st5();
    }
    while (q--) {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init(); solve();
}

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