Submission #1244655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244655		raphaelp	Passport (JOI23_passport)	C++20	100 / 100	951 ms	17396 KiB

passport

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

class SegTree
{
private:
    int N, type, inf;
    vector<int> st, node;
    int merge(int a, int b)
    {
        if (type == 0)
            return max(a, b);
        else
            return min(a, b);
    }
    int r(int x) { return (x << 1) + 1; }
    int l(int x) { return (x << 1); }
    void update(int L, int R, int a, int val, int x)
    {
        if (L > a || R < a)
            return;
        if (L == R)
        {
            st[x] = val;
            node[x] = L;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, l(x));
            update(m + 1, R, a, val, r(x));
            st[x] = merge(st[l(x)], st[r(x)]);
            if (st[x] == st[l(x)])
                node[x] = node[l(x)];
            else
                node[x] = node[r(x)];
        }
    }
    int RMQ(int L, int R, int a, int b, int val, int x)
    {
        if (L > b || R < a)
            return -1;
        if (L >= a && R <= b)
        {
            if (merge(st[x], val) == st[x])
                return node[x];
            else
                return -1;
        }
        int m = (L + R) / 2;
        return max(RMQ(L, m, a, b, val, l(x)), RMQ(m + 1, R, a, b, val, r(x)));
    }

public:
    SegTree(int x, int t)
    {
        N = pow(2, ceil(log2(x)));
        type = t;
        inf = 1000000000 * t;
        st.assign(2 * N, inf);
        node.assign(2 * N, -1);
    }
    void udpate(int a, int val) { update(0, N - 1, a, val, 1); }
    int RMQ(int a, int b, int val)
    {
        if (a > b)
            return -1;
        return RMQ(0, N - 1, a, b, val, 1);
    }
};

int main()
{
    int N;
    cin >> N;
    vector<int> L(N), R(N);
    for (int i = 0; i < N; i++)
    {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
    }
    vector<int> minL(N, 1000000000), minR(N, 1000000000);
    minL[0] = 0, minR[N - 1] = 0;
    SegTree MINN(N, 1), MAXX(N, 0);
    for (int i = 1; i < N; i++)
    {
        MINN.udpate(i, L[i]);
        MAXX.udpate(i, R[i]);
    }
    queue<int> Q;
    Q.push(0);
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        int y = MINN.RMQ(x + 1, N - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            minL[y] = minL[x] + 1;
            Q.push(y);
            y = MINN.RMQ(x + 1, N - 1, x);
        }
        y = MAXX.RMQ(0, x - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            minL[y] = minL[x] + 1;
            Q.push(y);
            y = MAXX.RMQ(0, x - 1, x);
        }
    }

    for (int i = 0; i < N - 1; i++)
    {
        MINN.udpate(i, L[i]);
        MAXX.udpate(i, R[i]);
    }
    Q.push(N - 1);
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        int y = MINN.RMQ(x + 1, N - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            minR[y] = minR[x] + 1;
            Q.push(y);
            y = MINN.RMQ(x + 1, N - 1, x);
        }
        y = MAXX.RMQ(0, x - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            minR[y] = minR[x] + 1;
            Q.push(y);
            y = MAXX.RMQ(0, x - 1, x);
        }
    }
    minL[0] = minR[N - 1] = 1;
    for (int i = 0; i < N; i++)
    {
        MINN.udpate(i, L[i]);
        MAXX.udpate(i, R[i]);
    }
    priority_queue<pair<int, int>> PQ;
    vector<int> ans(N, 1000000000);
    for (int i = 0; i < N; i++)
        PQ.push({-(minL[i] + minR[i] - 1), i});
    while (!PQ.empty())
    {
        int x = PQ.top().second, t = -PQ.top().first;
        PQ.pop();
        if (t >= ans[x])
            continue;
        ans[x] = t;
        MINN.udpate(x, 1000000000);
        MAXX.udpate(x, -1);
        int y = MINN.RMQ(x + 1, N - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            PQ.push({-ans[x] - 1, y});
            y = MINN.RMQ(x + 1, N - 1, x);
        }
        y = MAXX.RMQ(0, x - 1, x);
        while (y != -1)
        {
            MINN.udpate(y, 1000000000);
            MAXX.udpate(y, -1);
            PQ.push({-ans[x] - 1, y});
            y = MAXX.RMQ(0, x - 1, x);
        }
    }
    int Qs;
    cin >> Qs;
    for (int i = 0; i < Qs; i++)
    {
        int x;
        cin >> x;
        if (ans[x - 1] >= 1000000000)
            cout << -1 << '\n';
        else
            cout << ans[x - 1] << '\n';
    }
}

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