Advertisement
libobil

Untitled

Sep 26th, 2021
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn = 1e5+10;
  5.  
  6. int n, l, d;
  7. int a[maxn], b[maxn];
  8. pair < int, int > sorted[maxn];
  9.  
  10. bool check(int x) {
  11.  
  12.     int curr = 1;
  13.  
  14.     for (int i = 1 ; i <= n ; i++) {
  15.         if (sorted[i].second <= x) {
  16.  
  17.             b[curr] = sorted[i].first;
  18.             curr++;
  19.  
  20.         }
  21.     }
  22.  
  23.     b[0] = 0;
  24.     b[x+1] = l;
  25.  
  26.     for (int i = 1 ; i <= x+1 ; i++) {
  27.         if (b[i] - b[i-1] > d) return false;
  28.     }
  29.  
  30.     return true;
  31.  
  32. }
  33.  
  34. void solve() {
  35.  
  36.     for (int i = 1 ; i <= n ; i++) sorted[i] = {a[i], i};
  37.    
  38.     sort(sorted+1, sorted+1+n);
  39.  
  40.     int l = 1, r = n+1, mid;
  41.  
  42.     while (l < r - 1) {
  43.  
  44.         mid = (l+r)/2;
  45.         if (!check(mid)) l = mid;
  46.         else r = mid;
  47.  
  48.     }
  49.  
  50.     if (r == n+1) cout << -1 << '\n';
  51.     else cout << r << '\n';
  52.  
  53. }
  54.  
  55. void fast_io() {
  56.  
  57.     ios_base :: sync_with_stdio(0);
  58.     cin.tie(nullptr);
  59.     cout.tie(nullptr);
  60.     cerr.tie(nullptr);
  61.  
  62. }
  63.  
  64. void read() {
  65.  
  66.     cin >> n >> l >> d;
  67.     for (int i = 1 ; i <= n ; ++i) cin >> a[i];
  68.  
  69. }
  70.  
  71. int main () {
  72.  
  73.     fast_io();
  74.     read();
  75.     solve();
  76.  
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement