Submission #1258913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258913		nerrrmin	Passport (JOI23_passport)	C++20	48 / 100	840 ms	671504 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));

    }

    build(1, 1, n);
    for (int l = 1; l <= n; ++ l)
    {
        int minl = 1e9;
        int maxr = 0;
        for (int r = l; r <= n; ++ r)
        {
            minl = min(minl, lt[r]);
            maxr = max(maxr, rt[r]);

            g[minl][r].pb(make_pair(l, r));
            g[l][maxr].pb(make_pair(l, r));

            if(l < r)u[l+1][r].pb(make_pair(l, r));
            if(l < r)u[l][r-1].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: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46