Submission #804664

#	Time	Username	Problem	Language	Result	Execution time	Memory
804664		thimote75	Passport (JOI23_passport)	C++14	16 / 100	2074 ms	53964 KiB

passport

#include <bits/stdc++.h>

using namespace std;

using di = pair<int, int>;
using vd = vector<di>;

vd dis;

const int MAXN = 2600;
int dp[MAXN][MAXN];

int _compute (int l, int r) {
    if (l == 0 && r == dis.size() - 1) return 0;
    if (dp[l][r] != -1) return dp[l][r];

    dp[l][r] = 1e9;
    for (int i = l; i <= r; i ++) {
        dp[l][r] = min(
            dp[l][r],
            _compute(min(l, dis[i].first), max(r, dis[i].second)) + 1
        );
    }

    return dp[l][r];
}
int compute (int l, int r) {
    return _compute(l, r) >= 1e9 ? -1 : _compute(l, r);
}

int main () {
    int N;
    cin >> N;

    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            dp[i][j] = -1;

    dis = vd(N);

    for (int i = 0; i < N; i ++) {
        int l, r;
        cin >> l >> r;
        l --;
        r --;

        dis[i] = { l, r };
    }

    int Q; cin >> Q;
    for (int i = 0; i < Q; i ++) {
        int x; cin >> x;
        x --;

        cout << compute(x, x) << "\n";
    }
}

Compilation message (stderr)

passport.cpp: In function 'int _compute(int, int)':
passport.cpp:15:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (l == 0 && r == dis.size() - 1) return 0;
      |                   ~~^~~~~~~~~~~~~~~~~

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