Блог пользователя Ero-Sennin

Help needed in this question
Автор Ero-Sennin, история, 22 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится 
#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

→ Ответить