oj.uz

Submission #889125

# Submission time Handle Problem Language Result Execution time Memory
889125 2023-12-19T01:15:56 Z ducngo Passport (JOI23_passport) C++17
0 / 100
 80 ms 153684 KB 
#include <bits/stdc++.h>
#define getbit(i, j) ((i >> j) & 1)
#define maxn 200005
#define name "Passport"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r)
{
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n,q1;
int dpl[2505][2505],dpr[2505][2505],xd[2505][2505];
pair<int,int> a[maxn];
int f[2505][2505],l[2505][2505];
queue<pair<int,int>> q[maxn];

int tinh(int u,int v)
{
    if(u==1&&v==n)
    {
        f[u][v]=0;
        return 0;
    }
    if(u>v) return 1e9;
    if(xd[u][v]==1) return f[u][v];
    xd[u][v]=1;
    int val=1e9;
    if(u==v)
    {
        val=min(val,tinh(a[u].first,a[u].second)+1);
    }
    else
    {
        int d=u,c=dpr[u][v];
        val=min(val,tinh(d,c)+1);

        d=dpl[u][v],c=v;
        val=min(val,tinh(d,c)+1);
    }
    f[u][v]=val;
    return f[u][v];
}

void sub3()
{
    for(int i=1;i<=n;i++)
    {
        dpl[i][i]=a[i].first;
        dpr[i][i]=a[i].second;
        for(int j=i+1;j<=n;j++)
        {
            dpl[i][j]=dpl[i][j-1];
            if(dpl[i][j]>a[j].first)
            {
                dpl[i][j]=a[j].first;
            }

            dpr[i][j]=dpr[i][j-1];
            if(dpr[i][j]<a[j].second)
            {
                dpr[i][j]=a[j].second;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) f[i][j]=1e9;
    }

    for(int i=1;i<=n;i++) tinh(i,i);

    for(int i=1;i<=n;i++)
    {
        l[i][i]=f[i][i];
        for(int j=i+1;j<=n;j++) l[i][j]=min(l[i][j-1],f[j][j]);
    }
//    cout<<f[2][5]<<'\n';
    while(q1--)
    {
        int x;
        cin >> x;
        int d=a[x].first,c=a[x].second;
//        cout<<d<<' '<<c<<' '<<l[d][c]<<' '<<f[2][2]<<'\n';
        int val=min(f[x][x],l[d][c]+1);
        if(val>n) cout<<-1<<'\n';
        else cout<<val<<'\n';
    }

//    int xp;
//    cin >> xp;
//    int k=0;
//    f[xp][xp]=0;
//    q[0].push({xp,xp});
//    while(k<n)
//    {
//        while(q[k].size())
//        {
//            int u=q[k].front().first,v=q[k].front().second;
////            cout<<u<<' '<<v<<' '<<f[u][v]<<' '<<dpl[u][v]<<' '<<dpr[u][v]<<'\n';
//            q[k].pop();
//            if(u>v) continue;
//            if(f[u][v]!=k) continue;
//            if(u==v)
//            {
//                int d=a[u].first,c=a[u].second;
//                if(f[d][c]>k+1)
//                {
//                    f[d][c]=k+1;
//                    q[k+1].push({d,c});
//                }
//                continue;
//            }
//            int d=u,c=dpr[u][v];
////            if(u==2&&v==3) cout<<d<<' '<<c<<' '<<f[d][c]<<'\n';
//            if(f[d][c]>k+1)
//            {
//                f[d][c]=k+1;
//                q[k+1].push({d,c});
//            }
//            d=dpl[u][v],c=v;
////            if(u==2&&v==3) cout<<d<<' '<<c<<' '<<f[d][c]<<'\n';
//            if(f[d][c]>k+1)
//            {
//                f[d][c]=k+1;
//                q[k+1].push({d,c});
//            }
//            d=u,c=v;
//            if(d<c)
//            {
//
//                if(f[d+1][c]>k)
//                {
//                    f[d+1][c]=k;
//                    q[k].push({d+1,c});
//                }
////                if(u==2&&v==3) cout<<d<<' '<<c-1<<' '<<f[d][c-1]<<'\n';
//                if(f[d][c-1]>k)
//                {
//                    f[d][c-1]=k;
//                    q[k].push({d,c-1});
//                }
//            }
//        }
//        k++;
//    }
//    if(f[1][n]==1e9) cout<<-1;
//    else cout<<f[1][n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    cin >> q1;
    if(n<=2500)sub3();
}

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 144224 KB Output is correct
2 Correct 61 ms 144212 KB Output is correct
3 Correct 59 ms 144240 KB Output is correct
4 Incorrect 80 ms 140116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 144212 KB Output is correct
2 Correct 62 ms 144208 KB Output is correct
3 Correct 59 ms 144236 KB Output is correct
4 Correct 59 ms 144236 KB Output is correct
5 Correct 62 ms 144208 KB Output is correct
6 Correct 60 ms 144372 KB Output is correct
7 Correct 59 ms 144248 KB Output is correct
8 Correct 63 ms 144208 KB Output is correct
9 Correct 60 ms 144212 KB Output is correct
10 Correct 62 ms 144212 KB Output is correct
11 Correct 61 ms 153428 KB Output is correct
12 Correct 62 ms 153684 KB Output is correct
13 Incorrect 63 ms 153680 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 144212 KB Output is correct
2 Correct 62 ms 144208 KB Output is correct
3 Correct 59 ms 144236 KB Output is correct
4 Correct 59 ms 144236 KB Output is correct
5 Correct 62 ms 144208 KB Output is correct
6 Correct 60 ms 144372 KB Output is correct
7 Correct 59 ms 144248 KB Output is correct
8 Correct 63 ms 144208 KB Output is correct
9 Correct 60 ms 144212 KB Output is correct
10 Correct 62 ms 144212 KB Output is correct
11 Correct 61 ms 153428 KB Output is correct
12 Correct 62 ms 153684 KB Output is correct
13 Incorrect 63 ms 153680 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 144212 KB Output is correct
2 Correct 62 ms 144208 KB Output is correct
3 Correct 59 ms 144236 KB Output is correct
4 Correct 59 ms 144236 KB Output is correct
5 Correct 62 ms 144208 KB Output is correct
6 Correct 60 ms 144372 KB Output is correct
7 Correct 59 ms 144248 KB Output is correct
8 Correct 63 ms 144208 KB Output is correct
9 Correct 60 ms 144212 KB Output is correct
10 Correct 62 ms 144212 KB Output is correct
11 Correct 61 ms 153428 KB Output is correct
12 Correct 62 ms 153684 KB Output is correct
13 Incorrect 63 ms 153680 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 144224 KB Output is correct
2 Correct 61 ms 144212 KB Output is correct
3 Correct 59 ms 144240 KB Output is correct
4 Incorrect 80 ms 140116 KB Output isn't correct
5 Halted 0 ms 0 KB -