Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main() {
- int n, x;
- cin >> n >> x;
- vector<int> a(n);
- for(int &x : a) cin >> x;
- vector<vector<int>> to_query(n);
- vector<int> ans(n, -1);
- vector<pair<int,int>> v; // {a[i], i} increasing stack from backside
- for(int i = n-1; i >= 0; i--) {
- auto it = lower_bound(v.rbegin(), v.rend(), pair<int,int>{a[i]+x, -1});
- if(it != v.rend()) to_query[it->second].push_back(i);
- while(v.size() && v.back().first < a[i]) v.pop_back();
- v.push_back({a[i], i});
- }
- v.clear();
- for(int i = n -1; i >= 0; i--) {
- for(int j : to_query[i]) {
- // ye [i+1...n-1] m first index where a[index] >= a[j]+x ho seg_tree se bhi ho skta
- auto it = lower_bound(v.rbegin(), v.rend(), pair<int,int>{a[i]+x, -1});
- if(it != v.rend()) ans[j] = it->second;
- }
- while(v.size() && v.back().first < a[i]) v.pop_back();
- v.push_back({a[i], i});
- }
- for(int x : ans) cout << x << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement