Ero-Sennin's blog

Help needed in this question
By Ero-Sennin, history, 22 months ago, In English

Given an array a, find the number of pairs such that a[i]<=a[j]+k where i<j? Constraints — size of array <=1e5 I tried to use the concept of merge sort the way we use it to count inversions in an unsorted array, but I am getting WA. Could you help how to approach this problem and if you can provide code it would be very helpful.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it 
#include <bits/stdc++.h>
#include <bits/extc++.h> 
using namespace __gnu_pbds;
using namespace std;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

long long solve(int n, int k, vector<int>& a){
    ordered_set<pair<int, int>> os;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += os.order_of_key(make_pair(a[i] + k, INT_MAX));
        os.insert(make_pair(a[i], i));
    }
    return ans;
}

abusing ordered sets is fun

→ Reply