Submission #1226331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226331		minhpk	Passport (JOI23_passport)	C++20	48 / 100	1531 ms	1114112 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 if (z[l].first==z[r].first){
                 if (z[l].second>z[r].second){
                     st[i][j]=l;
                 }else{
                     st[i][j]=r;
                 }
              }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 if (z[l].second==z[r].second){
                 if (z[l].first<z[r].first){
                     st1[i][j]=l;
                 }else{
                     st1[i][j]=r;
                 }
              }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 if (z[idx1].first==z[idx2].first){
                 if (z[idx1].second>z[idx2].second){
                     return idx1;
                 }else{
                     return idx2;
                 }
              }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 if (z[idx1].second==z[idx2].second){
                 if (z[idx1].first<z[idx2].first){
                     return idx1;
                 }else{
                     return idx2;
                 }
    }else {
                 return idx2;
     }
}

int cnt[2501][2501];
int bruh=1e16;
struct node{
      int x,y,val;
};
vector <node> v[2501][2501];
void bfs(){
    for (int x=1;x<=a;x++){
       for (int y=x;y<=a;y++){
         int l=getmin(x,y);
         int r=getmax(x,y);
//         cout << x << " " << y << "\n";
         int u=z[l].first;
         int t=z[r].second;
         v[u][max(y,z[l].second)].push_back({x,y,1});
         v[min(x,z[r].first)][t].push_back({x,y,1});
         if (x!=y){
            v[x+1][y].push_back({x,y,0});
            v[x][y-1].push_back({x,y,0});
         }
       }
    }

}

void dijkstra(){
    for (int i=1;i<=a;i++){
         for (int j=1;j<=a;j++){
             cnt[i][j]=bruh;
         }
    }
    priority_queue< pair<int,pair<int,int>>, vector <pair<int,pair<int,int>>> ,greater<pair<int,pair<int,int>>> > q;
    q.push({1,{1,a}});
    cnt[1][a]=1;
    while (q.size()){
         pair<int,pair<int,int>> pos=q.top();
         q.pop();
         int val=pos.first;
         int x=pos.second.first;
         int y=pos.second.second;
         if (val>cnt[x][y]){
             continue;
         }
         for (auto p:v[x][y]){
              if (cnt[p.x][p.y]>val+p.val){
                  cnt[p.x][p.y]=val+p.val;
                  q.push({cnt[p.x][p.y],{p.x,p.y}});
              }
         }
    }
}

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();
    bfs();
    dijkstra();

    cin >> q;
    while (q--){
         int x;
         cin >> x;
         if (cnt[z[x].first][z[x].second]==bruh){
             cout << -1 << "\n";
         }else{
             cout << cnt[z[x].first][z[x].second] << "\n";
         }
    }
    return 0;
}

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