제출 #1183069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183069		sardor_salimov	Passport (JOI23_passport)	C++20	16 / 100	831 ms	1114112 KiB

passport

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

struct segtree {
    vector <ar <int, 3>> t;
    int n;
    void init(int sz) {
        n = sz; sz += 5;
        t.assign(sz << 2, {(int)1e9, 0, 0});
    }
    int qi, ql, qr;
    ar <int, 3> merge(const ar <int, 3> &a, const ar <int, 3> &b) {
        if (a[0] != b[0]) {
            if (a[0] < b[0])
                return a;
            return b;
        }
        if (a[1] > b[1])
            return a;
        return b;
    }
    void update(int v, int l, int r) {
        if (l == r)
            return t[v] = {ql, qr, qi}, void();
        int m = l + r >> 1;
        if (qi <= m)
            update(v << 1, l, m);
        else
            update(v << 1 | 1, m + 1, r);
        t[v] = merge(t[v << 1], t[v << 1 | 1]);
    }
    void upd(int i, int l, int r) {
        qi = i, ql = l, qr = r;
        update(1, 1, n);
    }
    ar <int, 3> get(int v, int l, int r) {
        if (ql <= l && r <= qr)
            return t[v];
        if (ql > r || l > qr)
            return t[0];
        int m = l + r >> 1;
        return merge(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)[2];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector <ar <int, 2>> rng(n + 1);
    vector <vector <int>> dp(n + 1, vector <int> (n + 1, 1e9)); 
    dp[1][n] = 0;
    segtree st[2];
    st[0].init(n);
    st[1].init(n);
    for (int i = 1; i <= n; i++)
        cin >> rng[i][0] >> rng[i][1], st[0].upd(i, rng[i][0], rng[i][1]), st[1].upd(i, -rng[i][1], -rng[i][0]);
    for (int add = n - 2; add >= 0; add--) {
        for (int l = 1; l + add <= n; l++) {
            int r = l + add;
            int tl = st[0].get(l, r), tr = st[1].get(l, r);
            dp[l][r] = min(dp[rng[tl][0]][max(r, rng[tl][1])], dp[min(l, rng[tr][0])][rng[tr][1]]) + 1;
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (dp[x][x] <= n)
            cout << dp[x][x] << '\n';
        else
            cout << -1 << '\n';
    }
}

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