제출 #1260884

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

passport

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;

#define ff first
#define ss second

bool compp(pii & a, pii & b) {
    return (a.second - a.first > b.second - b.first);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, a, b;
    cin >> n;

    vector<vector<int>> dp(n, vector<int>(n, 1e9));
    vector<vector<pii>> mini(n, vector<pii>(n, {1e9, 1e9}));
    vector<vector<pii>> maxi(n, vector<pii>(n, {-1e9, -1e9}));
    vector<vector<int>> mini_w(n, vector<int>(n, 1e9));
    vector<pii> seg;

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        a--;b--;
        seg.push_back({a, b});
    }


    dp[0][n - 1] = 0;
    vector<pair<int, int>> prz;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (i == 0 && j == n - 1) continue;
            if (i != j) mini[i][j] = mini[i][j - 1];
            if (i != j) maxi[i][j] = maxi[i][j - 1];
            if (seg[j].first < mini[i][j].first || (seg[j].first == mini[i][j].first && seg[j].second > mini[i][j].second)) mini[i][j] = seg[j];
            if (seg[j].second > maxi[i][j].second || (seg[j].second == maxi[i][j].second && seg[j] < maxi[i][j])) maxi[i][j] = seg[j];

            prz.push_back({i, j});
        }
    }

    sort(prz.begin(), prz.end(), compp);

    for (auto p : prz) {
        //for (int i = p.first; i <= p.second; i++) dp[p.first][p.second] = min(dp[p.first][p.second], dp[min(p.first, seg[i].first)][max(p.second, seg[i].second)] + 1);
        dp[p.first][p.second] = min(dp[min(mini[p.first][p.second].first, p.first)][max(mini[p.first][p.second].second, p.second)], dp[min(p.first, maxi[p.first][p.second].first)][maxi[p.first][p.second].second]) + 1;
        dp[p.first][p.second] = min(dp[p.first][p.second], mini_w[p.first][p.second] + 1);
        //cout << p.ff << ' ' << p.ss << ' ' << dp[p.ff][p.ss] << ' ' << mini[p.first][p.second].first << ' ' << mini[p.first][p.second].second  << ' ' << maxi[p.first][p.second].first << ' ' << maxi[p.first][p.second].second << '\n';
    }

    int q, val;
    cin >> q;

    while (q--) {
        cin >> val;
        val--;
        if (dp[val][val] >= 1e9) cout << -1 << '\n';
        else cout << dp[val][val] << '\n';
    }

    return 0;
}

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