Submission #1095815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095815		epicci23	Fire (BOI24_fire)	C++17	100 / 100	169 ms	32064 KiB

Main

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;
const int LOG = 20;

int lift[N][LOG];
vector<array<int,2>> v;
vector<array<int,2>> ar;
struct SegT{
  int n;
  vector<int> seg;
  SegT(int _n){
  	n=_n;
  	seg.assign(4*n+5,-1);
  }
  int merge(int a,int b){
  	if(a==-1 || b==-1) return (a==-1 ? b : a);
  	if(ar[a][1]>ar[b][1]) return a;
  	return b;
  }
  void update(int rt,int l,int r,int ind,int u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	 seg[rt]=merge(seg[rt],u);
  	 return;
  	}
  	int m=(l+r)/2;
  	update(rt*2,l,m,ind,u),update(rt*2+1,m+1,r,ind,u);
  	seg[rt]=merge(seg[rt*2],seg[rt*2+1]);
  }
  int query(int rt,int l,int r,int gl,int gr){
    if(r<gl || l>gr) return -1;
    if(l>=gl && r<=gr) return seg[rt];
    int m=(l+r)/2;
    return merge(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

void _(){
  int n,m;
  cin >> n >> m;
  for(int i=0;i<n;i++){
  	int a,b;
  	cin >> a >> b;
    if(a>b) b+=m;
    else{
     a+=m;
     b+=m;
    }
    v.push_back({a,b});
  }

  sort(all(v));
  
  vector<int> st(n,0);
  SegT T(2*n+5);
  ar.resize(n);
  vector<int> zip;
  for(int i=0;i<n;i++){
    zip.push_back(v[i][0]);
    zip.push_back(v[i][1]);
  }
  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  for(int i=0;i<n;i++){
  	if(v[i][0]<m && v[i][1]>=m) st[i]=1;
  	ar[i][0]=lower_bound(all(zip),v[i][0])-zip.begin();
  	ar[i][1]=lower_bound(all(zip),v[i][1])-zip.begin();
  }
  
  memset(lift,-1,sizeof(lift));

  for(int i=0;i<n;i++) T.update(1,0,2*n,ar[i][0],i);
  for(int i=0;i<n;i++){
  	lift[i][0]=T.query(1,0,2*n,ar[i][0]+1,ar[i][1]);
  	if(lift[i][0]!=-1 && ar[lift[i][0]][1]<=ar[i][1]) lift[i][0]=-1;
  	//cout << i << ' ' << lift[i][0] << '\n';
  }

  for(int i=1;i<LOG;i++)
  	for(int j=0;j<n;j++){
  	 if(lift[j][i-1]!=-1){
  	   lift[j][i]=lift[lift[j][i-1]][i-1];
  	 }
  	}

 int ans=(int)1e9;
  
 for(int i=0;i<n;i++){
   if(!st[i]) continue;
   int dur=m+v[i][0];
   //cout << i <<  ' ' << dur << '\n';
   int p=i,cur=1;
   for(int j=LOG-1;j>=0;j--){
    if(lift[p][j]==-1) continue;
    if(v[lift[p][j]][1]>=dur) continue;
    cur+=(1<<j);
    p=lift[p][j];
   }
   //cout << p << ' ' << cur << '\n';
   if(lift[p][0]!=-1 && v[lift[p][0]][1]>=dur) ans=min(ans,cur+1);
 }

 if(ans==(int)1e9) cout << -1 << '\n';
 else cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26