Submission #834540

#	Time	Username	Problem	Language	Result	Execution time	Memory
834540		kwongweng	Passport (JOI23_passport)	C++17	0 / 100	280 ms	14320 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

struct segtree{
  int sz; vi mx; vi a;
  void build(int v, int tl, int tr){
    if (tl==tr) {mx[v]=tl; return;}
    int tm=(tl+tr)/2;
    build(2*v,tl,tm); build(2*v+1,tm+1,tr);
    if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
    else mx[v]=mx[2*v+1];
  }
  void init(int n, vi A){
    sz=n; mx.assign(4*n,-1); a=A; build(1,0,n-1);
  }
  void rem(int v, int tl, int tr, int pos){
    if (tl==tr){mx[v]=-1; return;}
    int tm=(tl+tr)/2;
    if (pos<=tm) rem(2*v,tl,tm,pos);
    else rem(2*v+1,tm+1,tr,pos);
    if (mx[2*v] != -1 && mx[2*v+1] != -1){
      if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
      else mx[v]=mx[2*v+1];
    }else{
      if (mx[2*v]==-1) mx[v]=mx[2*v+1];
      else mx[v]=mx[2*v];
    }
  }
  void rem(int pos){rem(1,0,sz-1,pos);}
  int qry(int v, int tl, int tr, int l, int r){
    if (tl==l && tr==r) return mx[v];
    if (l>r) return -1;
    int tm=(tl+tr)/2;
    int L=qry(2*v,tl,tm,l,min(r,tm)), R=qry(2*v+1,tm+1,tr,max(l,tm+1),r);
    if (L==-1) return R;
    if (R==-1) return L;
    if (a[L]>=a[R]) return L;
    return R;
  }
  int qry(int l, int r){return qry(1,0,sz-1,l,r);}
};

void solve(){
  int n; cin>>n;
  vi l(n+1), r(n+1);
  FOR(i,1,n+1) cin>>l[i]>>r[i];
  FOR(i,1,n+1) l[i]=n-l[i];
  segtree stl, str;
  stl.init(n+1,l); str.init(n+1,r);
  vi d1(n+1,n+2); queue<int> bfs; 
  d1[1]=0; stl.rem(1); str.rem(1);
  FOR(i,2,n+1){
    if (n-l[i]==1){ // l[i]==1 (l[i] was changed into n-l[i] in line 55)
      stl.rem(i); str.rem(i); bfs.push(i); d1[i]=1;
    }
  }
  while (!bfs.empty()){
    int u = bfs.back(); bfs.pop();
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
      //cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
      //cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
      val=stl.qry(u,n);
    }
  }
  //FOR(i,1,n+1) cout<<d1[i]<<" "; cout<<"\n";

  vi dn(n+1,n+2); 
  stl.init(n+1,l); str.init(n+1,r);
  dn[n]=0; stl.rem(n); str.rem(n);
  FOR(i,1,n){
    if (r[i]==n){
      stl.rem(i); str.rem(i); bfs.push(i); dn[i]=1;
    }
  }
  while (!bfs.empty()){
    int u = bfs.back(); bfs.pop();
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
      val=stl.qry(u,n);
    }
  }
  //FOR(i,1,n+1) cout<<dn[i]<<" "; cout<<"\n";
  
  vi ans(n+1); FOR(i,1,n+1) ans[i]=d1[i]+dn[i]-1; ans[1]++; ans[n]++;
  int mn=ans[1]; FOR(i,2,n+1) mn=min(mn,ans[1]);
  stl.init(n+1,l); str.init(n+1,r);
  priority_queue<ii,vii,greater<ii>> pq;
  FOR(i,1,n+1){
    if (ans[i]<=n) pq.push({ans[i],i});
  }
  while (!pq.empty()){
    ii node = pq.top(); pq.pop();
    int u = node.se;
    if (ans[u] != node.fi) continue;
    int val = str.qry(1,u);
    while (val != -1 && r[val] >= u){
      stl.rem(val); str.rem(val); bfs.push(val);
      if (ans[val] > ans[u]+1){
        ans[val]=ans[u]+1; pq.push({ans[val],val});
      }
      val=str.qry(1,u);
    }
    val = stl.qry(u,n);
    while (val!=-1 && l[val] >= n-u){
      stl.rem(val); str.rem(val); bfs.push(val);
      if (ans[val] > ans[u]+1){
        ans[val]=ans[u]+1; pq.push({ans[val],val});
      }
      val=stl.qry(u,n);
    }
  }
  if (dn[1]>n) cout<<-1<<"\n";
  else cout<<dn[1]<<"\n"; 
  return;
  int q; cin>>q;
  while(q--){
    int x; cin>>x; 
    if (ans[x]>n) ans[x]=-1;
    cout<<ans[x]<<"\n";
  }
  
}

int main(){
	//MOD=MOD1;
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		  freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	  }
    int TC = 1;
    //cin >> TC; 
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
	
	return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:153:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:154:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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