2426. Number of Pairs Satisfying Inequality
You are given two 0-indexed integer arrays nums1 and nums2, each of size n, and an integer diff. Find the number of pairs (i, j) such that:
- 0 <= i < j <= n - 1 and
- nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.
Return the number of pairs that satisfy the conditions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| long long fenwick[101010];
long long query(long long n) {
long long res = 0;
while(n) {
res += fenwick[n];
n -= n & -n;
}
return res;
}
void update(long long n) {
while(n < 101010) {
fenwick[n] += 1;
n += n & -n;
}
}
class Solution {
public:
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
memset(fenwick, 0, sizeof fenwick);
vector<long long> A;
for(int i = 0; i < nums1.size(); i++) A.push_back(nums1[i] - nums2[i]);
long long mi = abs(*min_element(begin(A),end(A))) + 1 + 1e4;
for(int i = 0; i < A.size() ; i++) A[i] += mi;
long long res = 0;
for(int i = 0; i < A.size(); i++) {
res += query(A[i]);
update(A[i] - diff);
}
return res;
}
};
|
