oj.uz

Submission #805311

# Submission time Handle Problem Language Result Execution time Memory
805311 2023-08-03T15:03:05 Z Sharky Passport (JOI23_passport) C++17
0 / 100
 33 ms 50420 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;
    int x;
    cin >> x;
    for (int i = 1; i <= n; i++) {
        stmin.update(i, L[i], 1, n, 1);
        stmax.update(i, R[i], 1, n, 1);
    }
    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;
            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:94:5: warning: label 'bye' defined but not used [-Wunused-label]
   94 |     bye:{}
      |     ^~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

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