leetcode

commit ce6f945800069b9047d3c6ad526ff6724308f174
parent d48779f3d8402685b15837499abe366a0230a0cb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  4 Oct 2024 21:56:07 +0200

1 Random Problem

Diffstat:
A
Problems/3080.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/3080.cpp b/Problems/3080.cpp
@@ -0,0 +1,33 @@
+class Solution {
+  public:
+    vector<long long> unmarkedSumArray(vector<int> &nums, const vector<vector<int>> &queries) const {
+        const int n = size(nums), m = size(queries);
+        long long sum = accumulate(begin(nums), end(nums), 0ll);
+
+        const auto mark = [&](int idx) {
+            if (nums[idx] < 0) return false;
+            sum += nums[idx] = -nums[idx];
+            return true;
+        };
+
+        vector<pair<int, int>> pairs(n);
+        for (int i = 0; i < n; i++)
+            pairs[i] = {nums[i], i};
+        sort(begin(pairs), end(pairs));
+
+        int crnt = 0;
+        vector<long long> res(m);
+        for (int i = 0; i < m; i++) {
+            mark(queries[i][0]);
+
+            int k = queries[i][1];
+            while (crnt < n && k > 0) {
+                k -= mark(pairs[crnt++].second);
+            }
+
+            res[i] = sum;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1349,6 +1349,7 @@ for solving problems.
 |  3068  |    Hard    | [Find the Maximum Sum of Node Values](Problems/3068.cpp)                                           |
 |  3070  |   Medium   | [Count Submatrices with Top-Left Element and Sum Less Than k](Problems/3070.cpp)                   |
 |  3075  |   Medium   | [Maximize Happiness of Selected Children](Problems/3075.cpp)                                       |
+|  3080  |   Medium   | [Mark Elements on Array by Performing Queries](Problems/3080.cpp)                                  |
 |  3100  |   Medium   | [Water Bottles II](Problems/3100.cpp)                                                              |
 |  3101  |   Medium   | [Count Alternating Subarrays](Problems/3101.cpp)                                                   |
 |  3106  |   Medium   | [Lexicographically Smallest String After Operations With Constraint](Problems/3106.cpp)            |