Advertisement
vinayak7989

Untitled

Sep 29th, 2022
609
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.       int n, x;
  6.       cin >> n >> x;
  7.       vector<int> a(n);
  8.       for(int &x : a) cin >> x;
  9.      
  10.       vector<vector<int>> to_query(n);
  11.       vector<int> ans(n, -1);
  12.       vector<pair<int,int>> v; // {a[i], i} increasing stack from backside
  13.        
  14.       for(int i = n-1; i >= 0; i--) {
  15.             auto it = lower_bound(v.rbegin(), v.rend(), pair<int,int>{a[i]+x, -1});
  16.             if(it != v.rend()) to_query[it->second].push_back(i);
  17.             while(v.size() && v.back().first < a[i]) v.pop_back();
  18.             v.push_back({a[i], i});
  19.       }
  20.       v.clear();
  21.       for(int i = n -1; i >= 0; i--) {
  22.             for(int j : to_query[i]) {
  23.             // ye [i+1...n-1] m first index where a[index] >= a[j]+x ho seg_tree se bhi ho skta
  24.                   auto it = lower_bound(v.rbegin(), v.rend(), pair<int,int>{a[i]+x, -1});
  25.                   if(it != v.rend()) ans[j] = it->second;
  26.             }
  27.             while(v.size() && v.back().first < a[i]) v.pop_back();
  28.             v.push_back({a[i], i});
  29.       }
  30.       for(int x : ans) cout << x << " ";
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement