Submission #1217546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217546		noyancanturk	Passport (JOI23_passport)	C++20	6 / 100	256 ms	41488 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={-1,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];
  vector<int>v;
  for(int i=0;i<n;i++){
    if(a[i]==0){
      costleft[i]=0;
      v.clear();
      v.pb(i);
    }else{
      auto p=lower_bound(v.begin(),v.end(),a[i]);
      if(p==v.end()){
        costleft[i]=INT_MAX;
      }else{
        costleft[i]=p-v.begin()+1;
        while(v.back()!=*p){
          v.pop_back();
        }
        v.pb(i);
      }
    }
  }
  v.clear();
  for(int i=n-1;0<=i;i--){
    if(b[i]==n-1){
      costright[i]=0;
      v.clear();
      v.pb(i);
    }else{
      auto p=lower_bound(v.begin(),v.end(),b[i],greater<int>());
      if(p==v.end()){
        costright[i]=INT_MAX;
      }else{
        costright[i]=p-v.begin()+1;
        while(v.back()!=*p){
          v.pop_back();
        }
        v.pb(i);
      }
    }
  }
  stmin.build();
  stmax.build();
  int cost[n];
  for(int i=0;i<n;i++){
    cost[i]=costleft[i]+costright[i];
    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,0);
        if(cost[node]+1<cost[ind]){
          cost[ind]=cost[node]+1;
          pq.push({cost[ind],ind});
        }
      }else break;
    }
    while(node<n-1){
      auto[mn,ind]=stmin.query(node+1);
      if(mn<=node){
        stmin.update(ind,n);
        if(cost[node]+1<cost[ind]){
          cost[ind]=cost[node]+1;
          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: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46