Submission #1217572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217572		noyancanturk	Passport (JOI23_passport)	C++20	100 / 100	688 ms	44344 KiB

passport

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

struct{
  pii tree[4*lim];
  void build(){
    for(pii&p:tree)p={INT_MIN,0};
  }
  int P,VAL;
  pii update(int l,int r,int node){
    if(l==r)return tree[node]={VAL,l};
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)return tree[node]=max(update(l,mid,child),tree[child|1]);
    return tree[node]=max(tree[child],update(mid+1,r,child|1));
  }
  pii query(int l,int r,int node){
    if(r<=P)return tree[node];
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)return query(l,mid,child);
    return max(tree[child],query(mid+1,r,child|1));
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  pii query(int p){
    P=p;
    return query(0,lim-1,1);
  }
}stmax;

struct{
  pii tree[4*lim];
  void build(){
    for(pii&p:tree)p={INT_MAX,0};
  }
  int P,VAL;
  pii update(int l,int r,int node){
    if(l==r)return tree[node]={VAL,l};
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)return tree[node]=min(update(l,mid,child),tree[child|1]);
    return tree[node]=min(tree[child],update(mid+1,r,child|1));
  }
  pii query(int l,int r,int node){
    if(P<=l)return tree[node];
    int mid=l+r>>1,child=node<<1;
    if(mid+1<=P)return query(mid+1,r,child|1);
    return min(query(l,mid,child),tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  pii query(int p){
    P=p;
    return query(0,lim-1,1);
  }
}stmin;

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,q;
  cin>>n;
  int a[n],b[n];
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    a[i]--,b[i]--;
  }
  cin>>q;
  int c[q];
  for(int i=0;i<q;i++){
    cin>>c[i];
    c[i]--;
  }
  int costleft[n],costright[n];
  for(int i=0;i<n;i++){
    costleft[i]=costright[i]=INT_MAX;
  }
  queue<int>qq;
  for(int i=0;i<n;i++){
    if(a[i]==0){
      costleft[i]=0;
      qq.push(i);
    }
  }
  stmin.build();
  stmax.build();
  for(int i=0;i<n;i++){
    stmin.update(i,a[i]);
    stmax.update(i,b[i]);
  }
  while(qq.size()){
    int node=qq.front();
    qq.pop();
    while(node){
      auto[mx,ind]=stmax.query(node-1);
      if(node<=mx){
        stmax.update(ind,INT_MIN);
        if(costleft[ind]==INT_MAX){
          costleft[ind]=costleft[node]+1;
          qq.push(ind);
        }
      }else break;
    }
    while(node<n-1){
      auto[mn,ind]=stmin.query(node+1);
      if(mn<=node){
        stmin.update(ind,INT_MAX);
        if(costleft[ind]==INT_MAX){
          costleft[ind]=costleft[node]+1;
          qq.push(ind);
        }
      }else break;
    }
  }
  for(int i=0;i<n;i++){
    if(b[i]==n-1){
      costright[i]=0;
      qq.push(i);
    }
  }
  stmin.build();
  stmax.build();
  for(int i=0;i<n;i++){
    stmin.update(i,a[i]);
    stmax.update(i,b[i]);
  }
  while(qq.size()){
    int node=qq.front();
    qq.pop();
    while(node){
      auto[mx,ind]=stmax.query(node-1);
      if(node<=mx){
        stmax.update(ind,INT_MIN);
        if(costright[ind]==INT_MAX){
          costright[ind]=costright[node]+1;
          qq.push(ind);
        }
      }else break;
    }
    while(node<n-1){
      auto[mn,ind]=stmin.query(node+1);
      if(mn<=node){
        stmin.update(ind,INT_MAX);
        if(costright[ind]==INT_MAX){
          costright[ind]=costright[node]+1;
          qq.push(ind);
        }
      }else break;
    }
  }
  stmin.build();
  stmax.build();
  int cost[n];
  for(int i=0;i<n;i++){
    cost[i]=costleft[i]+costright[i];
    //cout<<costleft[i]<<' '<<costright[i]<<' '<<cost[i]<<'\n';
    stmin.update(i,a[i]);
    stmax.update(i,b[i]);
  }
  priority_queue<pii,vector<pii>,greater<pii>>pq;
  for(int i=0;i<n;i++){
    pq.push({cost[i],i});
  }
  while(pq.size()){
    auto[ds,node]=pq.top();
    pq.pop();
    if(ds!=cost[node])continue;
    while(node){
      auto[mx,ind]=stmax.query(node-1);
      if(node<=mx){
        stmax.update(ind,INT_MIN);
        if(cost[node]+1<cost[ind]){
          cost[ind]=cost[node]+1;
          //cout<<a[ind]<<' '<<b[ind]<<" <-- "<<a[node]<<' '<<b[node]<<'\n';
          pq.push({cost[ind],ind});
        }
      }else break;
    }
    while(node<n-1){
      auto[mn,ind]=stmin.query(node+1);
      if(mn<=node){
        stmin.update(ind,INT_MAX);
        if(cost[node]+1<cost[ind]){
          cost[ind]=cost[node]+1;
          //cout<<a[ind]<<' '<<b[ind]<<" <-- "<<a[node]<<' '<<b[node]<<'\n';
          pq.push({cost[ind],ind});
        }
      }else break;
    }
  }
  for(int i=0;i<n;i++){
    if(cost[i]>n-1)cost[i]=-2;
  }
  for(int i=0;i<q;i++){
    cout<<cost[c[i]]+1<<'\n';
  }
  // for(int i=0;i<n;i++){
  //   cout<<'\n'<<cost[i]+1;
  // }
}

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