leetcode

commit 1abf5ecf0e9c2ccf6a654bbb139c6a7802db7d1c
parent ba596d8b3febd098a838c274823f910043b25ae1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  2 Jan 2024 18:22:52 +0000

1 Random Problem

Diffstat:
A
Problems/1508.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 18 insertions(+), 0 deletions(-)
diff --git a/Problems/1508.cpp b/Problems/1508.cpp
@@ -0,0 +1,17 @@
+class Solution {
+    static const int MOD = 1E9 + 7;
+
+  public:
+    int rangeSum(const vector<int> &nums, int n, int left, int right) const {
+        vector<int> vec;
+        for (int i = 0; i < n; i++) {
+            for (int j = i, acc = 0; j < n; j++) {
+                vec.push_back(acc += nums[j]);
+            }
+        }
+
+        nth_element(vec.begin(), vec.begin() + left - 1, vec.end());
+        nth_element(vec.begin() + left, vec.begin() + right - 1, vec.end());
+        return accumulate(begin(vec) + left - 1, begin(vec) + right, 0ll) % MOD;
+    }
+};
diff --git a/README.md b/README.md
@@ -737,6 +737,7 @@ for solving problems.
 |  1498  |   Medium   | [Number of Subsequences That Satisfy the Given Sum Condition](Problems/1498.cpp)                   |
 |  1502  |    Easy    | [Can Make Arithmetic Progression From Sequence](Problems/1502.cpp)                                 |
 |  1503  |   Medium   | [Last Moment Before All Ants Fall Out of a Plank](Problems/1503.cpp)                               |
+|  1508  |   Medium   | [Range Sum of Sorted Subarray Sums](Problems/1508.cpp)                                             |
 |  1512  |    Easy    | [Number of Good Pairs](Problems/1512.cpp)                                                          |
 |  1514  |   Medium   | [Path with Maximum Probability](Problems/1514.cpp)                                                 |
 |  1517  |    Easy    | [Find Users With Valid E-Mails](Problems/1517.cpp)                                                 |