oj.uz

Submission #805332

# Submission time Handle Problem Language Result Execution time Memory
805332 2023-08-03T15:24:11 Z Sharky Passport (JOI23_passport) C++17
16 / 100
 2000 ms 50548 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Runtime error 42 ms 50548 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 13 ms 1716 KB Output is correct
12 Correct 17 ms 1748 KB Output is correct
13 Correct 15 ms 1876 KB Output is correct
14 Correct 12 ms 1804 KB Output is correct
15 Correct 16 ms 1892 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 13 ms 1716 KB Output is correct
12 Correct 17 ms 1748 KB Output is correct
13 Correct 15 ms 1876 KB Output is correct
14 Correct 12 ms 1804 KB Output is correct
15 Correct 16 ms 1892 KB Output is correct
16 Execution timed out 2084 ms 23236 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 13 ms 1716 KB Output is correct
12 Correct 17 ms 1748 KB Output is correct
13 Correct 15 ms 1876 KB Output is correct
14 Correct 12 ms 1804 KB Output is correct
15 Correct 16 ms 1892 KB Output is correct
16 Execution timed out 2084 ms 23236 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Runtime error 42 ms 50548 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -