leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0493.cpp (1391B)

0 class SegmentTree { 1 const int n; 2 vector<int> t = vector<int>(2 * n, 1); 3 4 public: 5 SegmentTree(const int n) : n(n) { 6 for (int i = n - 1; i > 0; i--) 7 t[i] = t[i * 2] + t[i * 2 + 1]; 8 } 9 10 int sum(int l, int r) const { 11 int res = 0; 12 13 for (l += n, r += n; l < r; l /= 2, r /= 2) { 14 if (l & 1) res += t[l++]; 15 if (r & 1) res += t[--r]; 16 } 17 18 return res; 19 } 20 21 void update(int p) { 22 for (t[p += n]--; p > 1; p /= 2) 23 t[p / 2] = t[p] + t[p ^ 1]; 24 } 25 }; 26 27 class Solution { 28 public: 29 int reversePairs(const vector<int> &nums) const { 30 const int n = size(nums); 31 32 // sort the array using index array 33 static int idxs[50001]; 34 iota(idxs, idxs + n, 0); 35 sort(idxs, idxs + n, [&](int a, int b) { return nums[a] < nums[b]; }); 36 37 static int rev[50001]; 38 for (int i = 0; i < n; i++) { 39 rev[idxs[i]] = i; 40 } 41 42 int res = 0; 43 SegmentTree seg(n); 44 for (int i = n - 1; i >= 0; i--) { 45 seg.update(rev[i]); 46 const auto cmp = [&](long long value, int &idx) { return value < nums[idx]; }; 47 const auto it = upper_bound(idxs, idxs + n, nums[i] * 2ll, cmp); 48 if (it == idxs + n) continue; 49 res += seg.sum(it - idxs, n); 50 } 51 52 return res; 53 } 54 };