Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int maxn = 1e5+10;
- int n, l, d;
- int a[maxn], b[maxn];
- pair < int, int > sorted[maxn];
- bool check(int x) {
- int curr = 1;
- for (int i = 1 ; i <= n ; i++) {
- if (sorted[i].second <= x) {
- b[curr] = sorted[i].first;
- curr++;
- }
- }
- b[0] = 0;
- b[x+1] = l;
- for (int i = 1 ; i <= x+1 ; i++) {
- if (b[i] - b[i-1] > d) return false;
- }
- return true;
- }
- void solve() {
- for (int i = 1 ; i <= n ; i++) sorted[i] = {a[i], i};
- sort(sorted+1, sorted+1+n);
- int l = 1, r = n+1, mid;
- while (l < r - 1) {
- mid = (l+r)/2;
- if (!check(mid)) l = mid;
- else r = mid;
- }
- if (r == n+1) cout << -1 << '\n';
- else cout << r << '\n';
- }
- void fast_io() {
- ios_base :: sync_with_stdio(0);
- cin.tie(nullptr);
- cout.tie(nullptr);
- cerr.tie(nullptr);
- }
- void read() {
- cin >> n >> l >> d;
- for (int i = 1 ; i <= n ; ++i) cin >> a[i];
- }
- int main () {
- fast_io();
- read();
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement