Submission #1260911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260911		SzymonKrzywda	Passport (JOI23_passport)	C++20	48 / 100	772 ms	1114112 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;
    cin >> n;

    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>()));
    vector<pii> seg;

    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        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 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: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46