Submission #805332

#	Time	Username	Problem	Language	Result	Execution time	Memory
805332		Sharky	Passport (JOI23_passport)	C++17	16 / 100	2084 ms	50548 KiB

passport

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

const int maxn = 2500+8;
int n, q, L[maxn], R[maxn];

struct segtree {
    int size = 1;
    vector<int> seg;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 5, 0);
    }
    void update(int pos, int val, int l, int r, int id) {
        if (l == r) {
            seg[id] = max(seg[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(pos, val, l, mid, id * 2);
        else update(pos, val, mid + 1, r, id * 2 + 1);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    int query(int ql, int qr, int l, int r, int id) {
        if (ql <= l && r <= qr) return seg[id];
        if (qr < l || r < ql) return 0;
        int mid = (l + r) >> 1;
        return max(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
} stmax;

struct segtree2 {
    int size = 1;
    vector<int> seg;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 5, 1e9);
    }
    void update(int pos, int val, int l, int r, int id) {
        if (l == r) {
            seg[id] = min(seg[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(pos, val, l, mid, id * 2);
        else update(pos, val, mid + 1, r, id * 2 + 1);
        seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
    }
    int query(int ql, int qr, int l, int r, int id) {
        if (ql <= l && r <= qr) return seg[id];
        if (qr < l || r < ql) return 1e9;
        int mid = (l + r) >> 1;
        return min(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
} stmin;

struct passport {
    int l, r, id;
    bool operator < (const passport& o) const {
        return id < o.id;
    }
};

int dp[maxn][maxn];

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> L[i] >> R[i];
    vector<passport> A;
    stmax.init(n + 1);
    stmin.init(n + 1);
    // sort(A.begin(), A.end());
    cin >> q;
    for (int i = 1; i <= n; i++) {
        stmin.update(i, L[i], 1, n, 1);
        stmax.update(i, R[i], 1, n, 1);
    }
    while (q--) {
        int x;
        cin >> x;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = 1e9;
        dp[x][x] = 0;
        for (int len = 0; len <= n - 1; len++) {
            for (int l = 1; l <= n - len; l++) {
                int r = l + len;
                for (int k = l; k <= r; k++) {
                    dp[min(L[k], l)][max(R[k], r)] = min(dp[min(L[k], l)][max(R[k], r)], dp[l][r] + 1);
                }
                // int rr = stmax.query(l, r, 1, n, 1);
                // int ll = stmin.query(l, r, 1, n, 1);
                // if (rr != 1e9) dp[l][rr] = min(dp[l][rr], dp[l][r] + 1);
                // if (ll != 0) dp[ll][r] = min(dp[ll][r], dp[l][r] + 1);
                // cout << l << " " << r << " " << dp[l][r] << "\n";
            }
        }
        if (dp[1][n] != 1e9) cout << dp[1][n] << "\n";
        else cout << "-1\n";
    }
    bye:{}
}

Compilation message (stderr)

passport.cpp: In function 'int32_t main()':
passport.cpp:99:5: warning: label 'bye' defined but not used [-Wunused-label]
   99 |     bye:{}
      |     ^~~

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