Submission #957447

#	Time	Username	Problem	Language	Result	Execution time	Memory
957447		rockstar	Passport (JOI23_passport)	C++17	54 / 100	871 ms	1048576 KiB

passport

//#pragma GCC optimize("O3,unroll-loops,inline")

#include <bits/stdc++.h>

//#define int long long
#define all(a) a.begin(), a.end()

using namespace std;

constexpr int inf = 1e9;

struct segment_tree_upd_segment_get_point {
    vector<int> tree;
    int n;

    segment_tree_upd_segment_get_point(int n_) {
        n = n_;
        tree.resize(4 * n, inf);
    }

    void upd(int v, int tl, int tr, int l, int r, int x) {
        if (r < tl || tr < l)
            return;
        if (l <= tl && tr <= r) {
            tree[v] = min(tree[v], x);
            return;
        }
        int tm = (tl + tr) / 2;
        upd(v * 2, tl, tm, l, r, x), upd(v * 2 + 1, tm + 1, tr, l, r, x);
    }

    int get(int v, int tl, int tr, int pos) {
        if (tl == tr)
            return tree[v];
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            return min(tree[v], get(v * 2, tl, tm, pos));
        else
            return min(tree[v], get(v * 2 + 1, tm + 1, tr, pos));
    }

    void upd(int l, int r, int x) {
        upd(1, 0, n - 1, l, r, x);
    }

    int get(int i) {
        return get(1, 0, n - 1, i);
    }
};

struct fenwick_tree {
    vector<int> tree;
    int n;

    fenwick_tree(int n_) {
        n = n_;
        tree.resize(n + 1, inf);
    }

    void upd(int i, int x) {
        ++i;
        for (; i > 0; i -= i & -i)
            tree[i] = min(tree[i], x);
    }

    int get(int i) {
        ++i;
        int x = inf;
        for (; i <= n; i += i & -i)
            x = min(x, tree[i]);
        return x;
    }
};

struct segment_tree_upd_point_get_segment {
    vector<int> tree;
    int n;

    segment_tree_upd_point_get_segment(int n_) {
        n = n_;
        tree.resize(4 * n, inf);
    }

    void upd(int v, int tl, int tr, int pos, int x) {
        if (tl == tr) {
            tree[v] = x;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            upd(v * 2, tl, tm, pos, x);
        else
            upd(v * 2 + 1, tm + 1, tr, pos, x);
        tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
    }

    int get(int v, int tl, int tr, int l, int r) {
        if (r < tl || tr < l)
            return inf;
        if (l <= tl && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        return min(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
    }

    void upd(int pos, int x) {
        upd(1, 0, n - 1, pos, x);
    }

    int get(int l, int r) {
        return get(1, 0, n - 1, l, r);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (auto &i: p)
        cin >> i.first >> i.second, --i.first, --i.second;
    int q;
    cin >> q;
    vector<int> k(q);
    for (int &i : k)
        cin >> i, --i;
    if (q == 1 && k[0] == 0) {
        multiset<int> now = {1};
        vector<vector<int>> upd(n + 1);
        upd[p[0].second + 1] = {1};
        for (int i = 0; i < n; ++i) {
            for (int j: upd[i])
                now.extract(j);
            if (now.empty()) {
                cout << -1;
                return 0;
            }
            int res = *now.begin();
            if (i == n - 1)
                cout << res;
            else {
                now.insert(res + 1);
                upd[p[i].second + 1].push_back(res + 1);
            }
        }
        return 0;
    }
    vector<vector<int>> left(n), right(n);
    for (int i = 0; i < n; ++i)
        left[p[i].first].push_back(i), right[p[i].second].push_back(i);
    vector<vector<int>> dp(n, vector<int>(n, inf));
    vector<fenwick_tree> dpl(n, fenwick_tree(n));
    vector<fenwick_tree> dpr(n, fenwick_tree(n));
    segment_tree_upd_point_get_segment mn(n);
    dp[0][n - 1] = 0;
    dpl[0].upd(n - 1 - (n - 1), 0);
    dpr[n - 1].upd(0, 0);
    for (int len = n; len >= 1; --len) {
        for (int l = 0; l < n; ++l) {
            int r = l + len - 1;
            if (r >= n)
                continue;
            dp[l][r] = min(min(dpl[l].get(n - 1 - r), dpr[r].get(l)), mn.get(l, r));
            for (int i: left[l]) {
                if (i <= r)
                    dpr[r].upd(i, dp[l][r] + 1);
                if (p[i].second == r)
                    mn.upd(i, dp[l][r] + 1);
            }
            for (int i: right[r])
                if (i >= l)
                    dpl[l].upd(n - 1 - i, dp[l][r] + 1);
        }
    }
    for (int i : k)
        cout << (dp[p[i].first][p[i].second] == inf ? -1 : dp[p[i].first][p[i].second] + 1) << ' ';
}

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