제출 #1258888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258888		nerrrmin	Passport (JOI23_passport)	C++20	0 / 100	755 ms	506596 KiB

passport

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 3e3 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, q;
int lt[maxn], rt[maxn];
int dp[maxn][maxn];
int tmin[maxn], tmax[maxn];

void build(int i, int l, int r)
{
    if(l == r)
    {
        tmin[i] = lt[l];
        tmax[i] = rt[l];
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    tmin[i] = min(tmin[2*i], tmin[2*i+1]);
    tmax[i] = max(tmax[2*i], tmax[2*i+1]);
}

int ql, qr;
int query_min(int i, int l, int r)
{
    if(qr < l || ql > r)return n+1;
    if(ql <= l && r <= qr)return tmin[i];
    int mid = (l + r)/2;
    return min(query_min(2*i, l, mid), query_min(2*i+1, mid+1, r));
}
int query_max(int i, int l, int r)
{
    if(qr < l || ql > r)return 0;
    if(ql <= l && r <= qr)return tmax[i];
    int mid = (l + r)/2;
    return max(query_max(2*i, l, mid), query_max(2*i+1, mid+1, r));
}
vector < pair < int, int > > g[maxn][maxn];
vector < pair < int, int > > u[maxn][maxn];
int used[maxn][maxn];
void bfs()
{
    queue < pair < int, int > > q;
    q.push(make_pair(1, n));

    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
            used[i][j] = 1e9;
    }
    used[1][n] = 1;
    while(!q.empty())
    {
        pair < int, int > w = q.front();
        q.pop();
        int l = w.first;
        int r = w.second;

       // cout << l << " " << r << endl;
        for (auto &[nbl, nbr]: u[l][r])
        {
            if(used[nbl][nbr] > used[l][r])
            {
                used[nbl][nbr] = used[l][r];
                q.push(make_pair(nbl, nbr));
            }
        }
        for (auto &[nbl, nbr]: g[l][r])
        {
            if(used[nbl][nbr] > used[l][r] + 1)
            {
                used[nbl][nbr] = used[l][r] + 1;
                q.push(make_pair(nbl, nbr));
            }
        }
    }
}
int main()
{
    speed();

    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> lt[i] >> rt[i];
        g[lt[i]][rt[i]].pb(make_pair(i, i));
        if(lt[i] < rt[i])u[lt[i]+1][rt[i]].pb(make_pair(lt[i], rt[i]));
        if(lt[i] < rt[i])u[lt[i]][rt[i]-1].pb(make_pair(lt[i], rt[i]));
    }

    build(1, 1, n);
    for (int l = 1; l <= n; ++ l)
    {
        for (int r = l+1; r <= n; ++ r)
        {
            ql = l;
            qr = r;
            int minl = query_min(1, 1, n);
            int maxr = query_max(1, 1, n);
            g[minl][r].pb(make_pair(l, r));
            g[l][maxr].pb(make_pair(l, r));
        }
    }
    bfs();
    cin >> q;
    while(q --)
    {
        int x;
        cin >> x;
        if(used[x][x] == 1e9)cout << -1 << endl;
        else cout << used[x][x] - 1 << endl;
    }
    return 0;
}

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