Submission #1226378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226378		minhpk	Passport (JOI23_passport)	C++20	0 / 100	46 ms	94280 KiB

passport

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

void update(int id,int l,int r,int x,int y,int t){
     if (x>r || y<l){
         return;
     }
     if (l>=x && y>=r){
         z[id+a].push_back({t,1});
         return;
     }
     int mid=(l+r)/2;
     update(id*2,l,mid,x,y,t);
     update(id*2+1,mid+1,r,x,y,t);
}

void build(int id,int l,int r){
    if (l==r){
        z[l].push_back({id+a,0});
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    z[id*2+a].push_back({id+a,0});
    z[id*2+1+a].push_back({id+a,0});
}
int cnt[4000001][3];
int bruh=1e16;

void bfs(int sta,int id){
    deque<int> q;
    q.push_front(sta);
    cnt[sta][id]=0;

    while (q.size()){
         int pos=q.front();
         q.pop_front();
         for (auto p:z[pos]){
//              if (id==1){
//                 cout << pos << " " << p.first << " " << p.second << "\n";
//              }
              if (cnt[p.first][id]==bruh){
                  cnt[p.first][id]=p.second+cnt[pos][id];
                  if (p.second){
                     q.push_back(p.first);
                  }else{
                     q.push_front(p.first);
                  }
              }
         }
    }
}

void dijkstra(){
    priority_queue<pair<int,int> ,vector <pair<int,int>> ,greater<pair<int,int>> > q;
    for (int i=1;i<=a;i++){
         if (cnt[i][2]<bruh){
             q.push({cnt[i][2],i});
         }
    }

    while (q.size()){
          pair<int,int> pos=q.top();
          q.pop();
          int val=pos.first;
          int pos1=pos.second;
          if (val>cnt[pos1][2]){
             continue;
          }
          for (auto p:z[pos1]){
               if (cnt[p.first][2]>val+p.second){
                   cnt[p.first][2]=val+p.second;
                   q.push({cnt[p.first][2],p.first});
               }
          }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         int x,y;
         cin >> x >> y;
         update(1,1,a,x,y,i);
    }
    build(1,1,a);

    for (int i=1;i<=a*log2(a)*2;i++){
         for (int j=0;j<=2;j++){
             cnt[i][j]=bruh;
         }
    }
    bfs(1,0);
    bfs(a,1);

    for (int i=1;i<=a;i++){
         if (cnt[i][1]+cnt[i][0]>=bruh){
             continue;
         }
       //  cout << i << " ";
         cnt[i][2]=cnt[i][1]+cnt[i][0]-(i!=1 && i!=a);
    }
    dijkstra();
    int c;
    cin >> c;
    while (c--){
         int x;
         cin >> x;
         if (cnt[x][2]>=bruh){
             cout << -1 << "\n";
         }else{
             cout << cnt[x][2] << "\n";
         }
    }
    return 0;
}

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