Submission #940286

#	Time	Username	Problem	Language	Result	Execution time	Memory
940286		GrandTiger1729	Passport (JOI23_passport)	C++17	100 / 100	1078 ms	105796 KiB

passport

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10, INF = 1e9 + 10;
struct SegTreeMin
{
    int l, r, mid;
    SegTreeMin *lc, *rc;
    int val = INF;
    SegTreeMin(int l_, int r_) : l(l_), r(r_)
    {
        mid = (l + r) / 2;
        if (l == r - 1)
        {
            return;
        }
        lc = new SegTreeMin(l, mid);
        rc = new SegTreeMin(mid, r);
    }
    ~SegTreeMin()
    {
        if (l == r - 1)
        {
            return;
        }
        delete lc;
        delete rc;
    }
    void update(int i, int u)
    {
        if (l == r - 1)
        {
            val = u;
            return;
        }
        if (i < mid)
        {
            lc->update(i, u);
        }
        else
        {
            rc->update(i, u);
        }
        val = min(lc->val, rc->val);
    }
    int query(int ll, int rr)
    {
        if (ll <= l && rr >= r)
        {
            return val;
        }
        int ret = INF;
        if (ll < mid)
        {
            ret = min(ret, lc->query(ll, rr));
        }
        if (mid < rr)
        {
            ret = min(ret, rc->query(ll, rr));
        }
        return ret;
    }
};
struct SegTree
{
    int l, r, mid;
    SegTree *lc, *rc;
    vector<int> val;
    SegTree(int l_, int r_) : l(l_), r(r_)
    {
        mid = (l + r) / 2;
        if (l == r - 1)
        {
            return;
        }
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
    }
    void add(int ll, int rr, int id)
    {
        if (ll <= l && rr >= r)
        {
            val.push_back(id);
            return;
        }
        if (ll < mid)
        {
            lc->add(ll, rr, id);
        }
        if (mid < rr)
        {
            rc->add(ll, rr, id);
        }
    }
    void query(int i, vector<int> &ans)
    {
        ans.insert(ans.end(), val.begin(), val.end());
        val.clear();
        if (l == r - 1)
        {
            return;
        }
        if (i < mid)
        {
            lc->query(i, ans);
        }
        else
        {
            rc->query(i, ans);
        }
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        l--;
        a[i] = make_pair(l, r);
    }
    vector<int> dpl(n, INF), dpr(n, INF);
    SegTreeMin stl(0, n);
    stl.update(0, 0);
    dpl[0] = 0;
    for (int i = 1; i < n; i++)
    {
        dpl[i] = min(dpl[i], a[i].first > 0 ? 1 + stl.query(a[i].first, i) : 0);
        stl.update(i, dpl[i]);
    }
    SegTreeMin str(0, n);
    str.update(n - 1, 0);
    dpr[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--)
    {
        dpr[i] = a[i].second < n ? 1 + str.query(i, a[i].second) : 0;
        str.update(i, dpr[i]);
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 0; i < n; i++)
    {
        pq.emplace(min(INF, min(dpl[i], 1 + stl.query(a[i].first, a[i].second)) + min(dpr[i], 1 + str.query(a[i].first, a[i].second))), i);
    }
    vector<int> ans(n, INF);
    SegTree st(0, n);
    for (int i = 0; i < n; i++)
    {
        st.add(a[i].first, a[i].second, i);
    }
    while (pq.size())
    {
        auto [d, i] = pq.top();
        pq.pop();
        if (d >= INF || ans[i] != INF)
        {
            continue;
        }
        ans[i] = d;
        vector<int> res;
        st.query(i, res);
        for (int j : res)
        {
            if (ans[j] == INF)
            {
                pq.emplace(d + 1, j);
            }
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
            int i;
            cin >> i;
            i--;
            cout << (ans[i] == INF ? -1 : ans[i] + 1) << '\n';
    }
    return 0;
    }

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