commit 6001ccf563bb24b7cbef75bfebea9504274012c2
parent 3635a481964340790a14ef5ce177a09dd7b7bebf
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 28 Oct 2024 18:45:26 +0100
Daily Problem, 2 Random, 1 Update
Diffstat:
5 files changed, 158 insertions(+), 23 deletions(-)
diff --git a/Problems/0327.cpp b/Problems/0327.cpp
@@ -0,0 +1,64 @@
+class SegmentTree {
+ const int n;
+ vector<long long> t = vector<long long>(2 * n);
+
+ public:
+ SegmentTree(int n) : n(n) {}
+
+ int sum(int l, int r) const {
+ int res = 0;
+
+ for (l += n, r += n; l < r; l /= 2, r /= 2) {
+ if (l & 1) res += t[l++];
+ if (r & 1) res += t[--r];
+ }
+
+ return res;
+ }
+
+ void update(int p) {
+ for (t[p += n]++; p > 1; p /= 2)
+ t[p / 2] = t[p] + t[p ^ 1];
+ }
+};
+
+class Solution {
+ public:
+ int countRangeSum(const vector<int> &nums, int lower, int upper) const {
+ const int n = size(nums);
+ vector<long long> prefix(n + 1);
+
+ for (int i = 0; i < n; i++) {
+ prefix[i + 1] = 1ll * prefix[i] + nums[i];
+ }
+
+ vector<long long> possible;
+ for (const long long n : prefix) {
+ possible.push_back(n);
+ possible.push_back(n - lower);
+ possible.push_back(n - upper);
+ }
+
+ const int m = size(possible);
+ static int idxs[300004];
+ iota(idxs, idxs + m, 0);
+ sort(idxs, idxs + m, [&](int a, int b) { return possible[a] < possible[b]; });
+
+ static int rev[300004];
+ for (int i = m - 2, cnt = rev[idxs[m - 1]] = m - 1; i >= 0; i--) {
+ if (possible[idxs[i]] != possible[idxs[i + 1]]) cnt--;
+ rev[idxs[i]] = cnt;
+ }
+
+ int res = 0;
+ SegmentTree seg(size(possible));
+ for (int i = 0; i <= n; i++) {
+ const int low = rev[i * 3 + 2];
+ const int high = rev[i * 3 + 1];
+ res += seg.sum(low, high + 1);
+ seg.update(rev[i * 3]);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0493.cpp b/Problems/0493.cpp
@@ -1,11 +1,9 @@
class SegmentTree {
const int n;
- vector<int> t = vector<int>(2 * n);
+ vector<int> t = vector<int>(2 * n, 1);
public:
- SegmentTree(const vector<int> nums) : n(size(nums)) {
- for (int i = 0; i < n; i++)
- t[n + i] = nums[i];
+ SegmentTree(const int n) : n(n) {
for (int i = n - 1; i > 0; i--)
t[i] = t[i * 2] + t[i * 2 + 1];
}
@@ -32,33 +30,24 @@ class Solution {
int reversePairs(const vector<int> &nums) const {
const int n = size(nums);
+ // sort the array using index array
static int idxs[50001];
iota(idxs, idxs + n, 0);
sort(idxs, idxs + n, [&](int a, int b) { return nums[a] < nums[b]; });
- vector<int> count; // count the number of each different value
- map<long long, int> um; // map each number to its position in sorted unique array
- int diff = 0, prev = nums[idxs[0]], cnt = 1;
- for (int i = 1; i < n; i++, cnt++) {
- const int crnt = nums[idxs[i]];
- if (crnt == prev) continue;
-
- um[prev] = size(count);
- count.push_back(cnt);
- prev = crnt;
- cnt = 0;
+ static int rev[50001];
+ for (int i = 0; i < n; i++) {
+ rev[idxs[i]] = i;
}
- um[prev] = size(count);
- count.push_back(cnt);
int res = 0;
- SegmentTree seg(count); // tree is indexed by position in sorted array
+ SegmentTree seg(n);
for (int i = n - 1; i >= 0; i--) {
- // remove current element, and check for left pair in the rest
- seg.update(um[nums[i]]);
- const auto it = um.upper_bound(nums[i] * 2ll);
- if (it == end(um)) continue;
- res += seg.sum(it->second, size(count));
+ seg.update(rev[i]);
+ const auto cmp = [&](long long value, int &idx) { return value < nums[idx]; };
+ const auto it = upper_bound(idxs, idxs + n, nums[i] * 2ll, cmp);
+ if (it == idxs + n) continue;
+ res += seg.sum(it - idxs, n);
}
return res;
diff --git a/Problems/0699.cpp b/Problems/0699.cpp
@@ -0,0 +1,59 @@
+class SegmentTree {
+ const int n;
+ vector<int> t = vector<int>(2 * n);
+
+ public:
+ SegmentTree(int n) : n(n) {}
+
+ int sum(int l, int r) const {
+ int res = 0;
+
+ for (l += n, r += n; l < r; l /= 2, r /= 2) {
+ if (l & 1) res = max(res, t[l++]);
+ if (r & 1) res = max(res, t[--r]);
+ }
+
+ return res;
+ }
+
+ void update(int p, int val) {
+ for (t[p += n] = val; p > 1; p /= 2)
+ t[p / 2] = max(t[p], t[p ^ 1]);
+ }
+};
+
+class Solution {
+ public:
+ vector<int> fallingSquares(const vector<vector<int>> &positions) const {
+ vector<int> possible;
+ for (const auto &pos : positions) {
+ possible.push_back(pos[0]);
+ possible.push_back(pos[0] + pos[1]);
+ }
+
+ const int m = size(possible);
+ static int idxs[2001];
+ iota(idxs, idxs + m, 0);
+ sort(idxs, idxs + m, [&](int a, int b) { return possible[a] < possible[b]; });
+
+ static int rev[2001];
+ for (int i = m - 2, cnt = rev[idxs[m - 1]] = m - 1; i >= 0; i--) {
+ if (possible[idxs[i]] != possible[idxs[i + 1]]) cnt--;
+ rev[idxs[i]] = cnt;
+ }
+
+ int maxi = 0;
+ vector<int> res;
+ SegmentTree seg(m);
+ for (int i = 0; i < size(positions); i++) {
+ const int a = rev[i * 2], b = rev[i * 2 + 1];
+ const int crnt = positions[i][1] + seg.sum(a, b);
+ res.push_back(maxi = max(maxi, crnt));
+ for (int i = a; i < b; i++) {
+ seg.update(i, crnt);
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2501.cpp b/Problems/2501.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ int longestSquareStreak(vector<int> &nums) {
+ static int seen[100001];
+
+ memset(seen, 0x00, sizeof(seen));
+ sort(begin(nums), end(nums));
+
+ int res = 0;
+ for (int i = 0; i < size(nums); i++) {
+ const int crnt = nums[i];
+ if (crnt < 317) {
+ seen[crnt * crnt] = seen[crnt] + 1;
+ }
+ res = max(res, seen[crnt]);
+ }
+
+ return res ? res + 1 : -1;
+ }
+};
diff --git a/README.md b/README.md
@@ -297,6 +297,7 @@ reference and a base for solving problems.
| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
| 0322 | Medium | [Coin Change](Problems/0322.cpp) |
| 0326 | Easy | [Power of Three](Problems/0326.cpp) |
+| 0327 | Hard | [Count of Range Sum](Problems/0327.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
| 0330 | Hard | [Patching Array](Problems/0330.cpp) |
| 0332 | Hard | [Reconstruct Itinerary](Problems/0332.cpp) |
@@ -499,6 +500,7 @@ reference and a base for solving problems.
| 0690 | Medium | [Employee Importance](Problems/0690.cpp) |
| 0692 | Medium | [Top K Frequent Words](Problems/0692.cpp) |
| 0695 | Medium | [Max Area of Island](Problems/0695.cpp) |
+| 0699 | Hard | [Falling Squares](Problems/0699.cpp) |
| 0700 | Easy | [Search in a Binary Search Tree](Problems/0700.cpp) |
| 0701 | Medium | [Insert into a Binary Search Tree](Problems/0701.cpp) |
| 0703 | Easy | [Kth Largest Element in a Stream](Problems/0703.cpp) |
@@ -1280,6 +1282,7 @@ reference and a base for solving problems.
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
| 2498 | Medium | [Frog Jump II](Problems/2498.cpp) |
+| 2501 | Medium | [Longest Square Streak in an Array](Problems/2501.cpp) |
| 2517 | Medium | [Maximum Tastiness of Candy Basket](Problems/2517.cpp) |
| 2526 | Medium | [Find Consecutive Integers from a Data Stream](Problems/2526.cpp) |
| 2527 | Medium | [Find Xor-Beauty of Array](Problems/2527.cpp) |
