Submission #1313204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313204		rythm_of_knight	Passport (JOI23_passport)	C++17	48 / 100	2096 ms	196572 KiB

passport

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
const int inf = 1e9;
int mn[20][N], mx[20][N], L[N], R[N], res[N];
map <ar <int, 2>, int> mp;

int getmx(int l, int r) {
    int lg = __lg(r - l + 1);
    return max(mx[lg][l], mx[lg][r - (1 << lg) + 1]);
}

int getmn(int l, int r) {
    int lg = __lg(r - l + 1);
    return min(mn[lg][l], mn[lg][r - (1 << lg) + 1]);
}

int get(int l, int r) {
    if (mp.count({l, r}))
        return mp[{l, r}];
    int tl = getmn(l, r), tr = getmx(l, r), ans = inf;
    if (tl < l) {
        ans = min(ans, get(tl, r) + 1);
        for (int i = tl; i < l; i++) {
            if (L[i] <= tl && r <= R[i]) {
                ans = min(ans, res[i] + 1);
            }
        }
    }
    if (r < tr) {
        ans = min(ans, get(l, tr) + 1);
        for (int i = r + 1; i <= tr; i++) {
            if (L[i] <= l && tr <= R[i]) {
                ans = min(ans, res[i] + 1);
            }
        }
    }
    return mp[{l, r}] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector <ar <int, 2>> b;
    for (int i = 1; i <= n; i++) {
        res[i] = inf;
        cin >> L[i] >> R[i];
        mn[0][i] = L[i];
        mx[0][i] = R[i];
        b.push_back({R[i] - L[i], i});
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            int m = j + (1 << i - 1);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][m]);
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][m]);
        }
    }
    mp[{1, n}] = 0;
    sort(all(b));
    reverse(all(b));
    for (auto cur : b) {
        int i = cur[1];
        res[i] = get(L[i], R[i]) + 1;
        for (int j = L[i]; j <= R[i]; j++)
            res[i] = min(res[i], res[j] + 1);
    }
    for (int i = 1; i <= n; i++)
        if (res[i] == inf + 1)
            res[i] = -1;
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << res[x] << '\n';
    }
}

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