제출 #1226305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226305		minhpk	Passport (JOI23_passport)	C++20	0 / 100	389 ms	138708 KiB

passport

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,q;
pair<int,int> z[1000005];

int st[200001][21];
int st1[200001][21];
int logarit[1000005];

void buildst(){
    for (int i=1;i<=a;i++){
        st[i][0]=i;
    }
    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=a;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];
              if (z[l].first<z[r].first){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}

void buildst1(){
    for (int i=1;i<=a;i++){
        st1[i][0]=i;
    }
    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=a;i++){
              int l=st1[i][j-1];
              int r=st1[i+(1<<(j-1))][j-1];
              if (z[l].second>z[r].second){
                 st1[i][j]=l;
              }else{
                 st1[i][j]=r;
              }
         }
    }
}

int getmin(int x,int y){
    int j=logarit[y-x+1];
    int idx1=st[x][j];
    int idx2=st[y-(1<<j)+1][j];
    if (z[idx1].first<z[idx2].first){
        return idx1;
    }else{
        return idx2;
    }
}

int getmax(int x,int y){
    int j=logarit[y-x+1];
    int idx1=st1[x][j];
    int idx2=st1[y-(1<<j)+1][j];
    if (z[idx1].second>z[idx2].second){
        return idx1;
    }else{
        return idx2;
    }
}

int cnt[2501][2501];
int bruh=1e16;
void bfs(int sta){
    for (int i=1;i<=a;i++){
         for (int j=i;j<=a;j++){
              cnt[i][j]=0;
         }
    }
    queue<pair<int,int>> q;
    q.push({z[sta].first,z[sta].second});
    cnt[z[sta].first][z[sta].second]=1;
    while (q.size()){
         auto[x,y]=q.front();
         q.pop();
         int l=getmin(x,y);
         int r=getmax(x,y);
//         cout << x << " " << y << "\n";
         int u=z[l].first;
         int v=z[r].second;
         if (!cnt[z[l].first][max(y,z[l].second)]){
             cnt[z[l].first][max(y,z[l].second)]=cnt[x][y]+1;
             q.push({z[l].first,max(y,z[l].second)});
         }
         if (!cnt[min(x,z[r].second)][z[r].second]){
             cnt[min(x,z[r].second)][z[r].second]=cnt[x][y]+1;
             q.push({min(x,z[r].second),z[r].second});
         }

         if (z[l].second==z[r].second){
             if (!cnt[u][v]){
                cnt[u][v]=cnt[x][y]+1;
                q.push({u,v});
             }
         }

          if (z[l].first==z[r].first){
             if (!cnt[u][v]){
                cnt[u][v]=cnt[x][y]+1;
                q.push({u,v});
             }
         }
    }
//    cout << cnt[2][4] << "\n";
    if (!cnt[1][a]){
        cout << -1 << "\n";
    }else{
        cout << cnt[1][a] << "\n";
    }
}

void bfs1(int sta){
    for (int i=1;i<=a;i++){
         for (int j=i;j<=a;j++){
              cnt[i][j]=0;
         }
    }
    queue<pair<int,int>> q;
    q.push({z[sta].first,z[sta].second});
    cnt[z[sta].first][z[sta].second]=1;
    while (q.size()){
         auto[x,y]=q.front();
         q.pop();
         for (int i=x;i<=y;i++){
              int nx=min(x,z[i].first);
              int ny=max(y,z[i].second);
         }
    }
//    cout << cnt[2][4] << "\n";
    if (!cnt[1][a]){
        cout << -1 << "\n";
    }else{
        cout << cnt[1][a] << "\n";
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
    }
    logarit[2]=1;
    for (int i=3;i<=1000000;i++){
         logarit[i]=logarit[i/2]+1;
    }
    buildst();
    buildst1();
    cin >> q;
    while (q--){
         int x;
         cin >> x;
         bfs(x);
    }
    return 0;
}

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