제출 #1260922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260922		SzymonKrzywda	Passport (JOI23_passport)	C++20	6 / 100	19 ms	1864 KiB

passport

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

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

#define ff first
#define ss second

const int base = 1 << 13;
int tree[base * 2];

void edit(int v, int val) {
    v += base;
    tree[v] = val;
    v /= 2;
    while (v) {
        tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
        v /= 2;
    }
}
int query(int l, int r) {
    l += base - 1;
    r += base + 1;

    int w = 1e9;
    while (l / 2 != r / 2) {
        if (l % 2 == 0) w = min(w, tree[l + 1]);
        if (r % 2 == 1) w = min(w, tree[r - 1]);
        l /= 2;
        r /= 2;
    }

    return w;
}


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, q;
    cin >> n;
    vector<pii> seg(n);
    for (int i = 0; i < n; i++) {
        cin >> seg[i].first >> seg[i].second;
        seg[i].first--;
        seg[i].second--;
    }
    cin >> q;
    vector<int> zap(q);

    for (int i = 0; i < q; i++) {
        cin >> zap[i];
        zap[i]--;
    }

    if (q == 1 && zap[0] == 0) {
        int maxi = 0, akt = 0, new_maxi = 0, ile = 0;

        while (akt < n) {
            while (akt <= maxi) {
                new_maxi = max(new_maxi, seg[akt].second);
                akt++;
            }
            //cout << maxi << ' ' << ile << ' ' << akt << '\n';

            if (new_maxi == maxi) break;
            maxi = new_maxi;
            ile++;
        }

        if (akt == n) cout << ile << '\n';
        else cout << -1 << '\n';
        return 0;
        

    }


    for (int i = 0; i < base * 2; i++) tree[i] = 1e9;

    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<vector<int>>> punkty(n, vector<vector<int>>(n, vector<int>()));
    

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


    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], query(p.first, p.second) + 1);
        for (int pkt : punkty[p.first][p.second]) {
            edit(pkt, dp[p.first][p.second]);
        }
        //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 val;

    for (int val : zap) {
        if (dp[val][val] >= 1e9) cout << -1 << '\n';
        else cout << dp[val][val] << '\n';
    }

    return 0;
}

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