Submission #1313212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313212		rythm_of_knight	Passport (JOI23_passport)	C++17	48 / 100	2105 ms	256136 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]);
}

struct segtree {
    vector <int> t;
    int n;
    segtree (int sz) {
        n = sz++;
        t.assign(sz << 2, inf);
    }
    int qi, qx, ql, qr;
    void update(int v, int l, int r) {
        if (l == r)
            return t[v] = qx, void();
        int m = l + r >> 1;
        if (qi <= m)
            update(v << 1, l, m);
        else
            update(v << 1 | 1, m + 1, r);
        t[v] = min(t[v << 1], t[v << 1 | 1]);
    }
    void update(int i, int x) {
        qi = i, qx = x;
        update(1, 1, n);
    }
    int get(int v, int l, int r) {
        if (ql <= l && r <= qr)
            return t[v];
        if (ql > r || l > qr)
            return inf;
        int m = l + r >> 1;
        return min(get(v << 1, l, m), get(v << 1 | 1, m + 1, r));
    }
    int get(int l, int r) {
        ql = l, qr = r;
        return get(1, 1, n);
    }
};
segtree st(N);

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);
        ans = min(ans, st.get(tl, l - 1) + 1);
    }
    if (r < tr) {
        ans = min(ans, get(l, tr) + 1);
        ans = min(ans, st.get(r + 1, tr) + 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;
        res[i] = min(res[i], st.get(L[i], R[i]) + 1);
        st.update(i, res[i]);
    }
    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