oj.uz

Submission #999232

# Submission time Handle Problem Language Result Execution time Memory
999232 2024-06-15T08:32:27 Z AlperenT_ Fire (BOI24_fire) C++17
0 / 100
 1 ms 348 KB 
#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 = 1e9  , 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});
  } 
  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[i][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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -