Submission #855147

#	Time	Username	Problem	Language	Result	Execution time	Memory
855147		boris_mihov	Passport (JOI23_passport)	C++17	54 / 100	631 ms	381220 KiB

passport

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 2500 + 10;
const int MAXN2 = 200000 + 10;
const int INF  = 1e9;

int n, q;
int l[MAXN2];
int r[MAXN2];
int dist[MAXN * MAXN];
bool vis[MAXN * MAXN];

int encode(int l, int r)
{
    return (l - 1) * n + r;
}

std::vector <std::pair <int,int>> g[MAXN * MAXN];
std::deque <int> dq;
void solve()
{
    if (n > 2500)
    {
        std::cin >> q;
        int ptr = 1;
        int maxR = r[1];
        int cnt = 0;

        while (ptr < n)
        {
            if (maxR <= ptr)
            {
                cnt = -1;
                break;
            }

            cnt++;
            int newMaxR = 0;
            while (ptr + 1 <= maxR)
            {
                ptr++;
                newMaxR = std::max(newMaxR, r[ptr]);
            }   

            maxR = newMaxR;
        }

        std::cout << cnt << '\n';
        return;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        int maxR = 0;
        int minL = n + 1;
        for (int j = i ; j <= n ; ++j)
        {
            maxR = std::max(maxR, r[j]);
            minL = std::min(minL, l[j]);
            g[encode(minL, j)].push_back({encode(i, j), 1});
            g[encode(i, maxR)].push_back({encode(i, j), 1});
            g[encode(l[i], r[i])].push_back({encode(i, j), 1});
            if (i != j) g[encode(i + 1, j)].push_back({encode(i, j), 0});
        }
    }

    std::fill(dist, dist + MAXN * MAXN, INF);
    dq.push_back(encode(1, n));
    dist[encode(1, n)] = 0;

    while (!dq.empty())
    {
        int top = dq.front();
        dq.pop_front();

        if (vis[top]) continue;
        vis[top] = true;

        for (const auto &[u, d] : g[top])
        {
            if (d == 0 && dist[u] > dist[top])
            {
                dist[u] = dist[top];
                dq.push_front(u);
            }

            if (d == 1 && dist[u] > dist[top] + d)
            {
                dist[u] = dist[top] + d;
                dq.push_back(u);
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (dist[encode(i, i)] == INF)
        {
            dist[encode(i, i)] = -1;
        }
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        int idx;
        std::cin >> idx;
        std::cout << dist[encode(idx, idx)] << '\n';
    }
}  

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }

    std::cin >> q;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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