Submission #999244

#	Time	Username	Problem	Language	Result	Execution time	Memory
999244		AlperenT_	Fire (BOI24_fire)	C++17	100 / 100	140 ms	38260 KiB

Main

#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define ll long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 1 ;
int n  , m , nx[maxn][lg+1] ;
vector <pii> v1 , v2 ;
vector <int> cm ;

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);   
  cin >> n >> m ;
  rep(i ,1 ,n){
    int l ,r ;
    cin >> l >>r ;
    if(l > r)r += m ;
    v1.pb({l,-r});
  } 
  sort(all(v1)) ;
  rep(i , 0, sz(v1)-1){
    if(sz(v2)!=0 && v2.back().S >= -v1[i].S){
      continue ;
    }
    v2.pb({v1[i].F , -v1[i].S}) ;
  }
  for(auto [l,r] : v2){
    cm.pb(l);
    cm.pb(r) ;
  }
  sort(all(cm)) ;
  cm.resize(unique(all(cm)) - cm.begin()) ;
  rep(i , 0 ,sz(cm)-1){
    int id = lower_bound(all(v2) , (pii){cm[i]+1 , -inf}) - v2.begin() - 1;
    if(id==-1 || v2[id].S <= cm[i]){
      nx[i][0] = -1 ;
      continue ;
    }
    nx[i][0] = lower_bound(all(cm) , v2[id].S) - cm.begin() ;   
  }
  rep(j , 1, lg){
    rep(i ,0 ,sz(cm)-1){
      if(nx[i][j-1] == -1){
        nx[i][j] = -1;
        continue ;
      }
      nx[i][j] = nx[nx[i][j-1]][j-1] ; 
    }
  }
  int mn = inf ;
  rep(i , 0, sz(cm)-1){
    int ans =1 , v = i;
    per( j, lg , 0){
      if(nx[v][j] == -1 || cm[nx[v][j]]-cm[i] >= m){
        continue ;
      }
      v=  nx[v][j] ;
      ans += (1<<j) ;
    }
    if(nx[v][0] == -1)continue ;
    mn = min(mn , ans); 
  }
  if(mn == inf){
    cout << "-1\n";
  }else{
    cout << mn << "\n" ;
  }
}
/*

*/

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