leetcode

commit 20eb2b305ef509a7ca401894634abe3628c40ba2
parent 55d62ce6e2cdf07e1fcb943120025a96e734d461
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 21 Jun 2024 12:29:29 +0200

1 Random Problem

Diffstat:
A
Problems/1943.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/1943.cpp b/Problems/1943.cpp
@@ -0,0 +1,28 @@
+class Solution {
+  public:
+    vector<vector<long long>> splitPainting(const vector<vector<int>> &segments) const {
+        static long long prefix[100002];
+        static bool seen[100002];
+
+        memset(seen, 0x00, sizeof(seen));
+        memset(prefix, 0x00, sizeof(prefix));
+        for (const auto seg : segments) {
+            prefix[seg[0]] += seg[2];
+            prefix[seg[1]] -= seg[2];
+
+            seen[seg[0]] = seen[seg[1]] = 1;
+        }
+
+        vector<vector<long long>> res;
+        long long crnt = 0, prev = 0;
+        for (int i = 1; i < 100002; i++) {
+            if (crnt && seen[i]) {
+                res.push_back({prev, i, crnt});
+            }
+            if (seen[i]) prev = i;
+            crnt += prefix[i];
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1012,6 +1012,7 @@ for solving problems.
 |  1926  |   Medium   | [Nearest Exit from Entrance in Maze](Problems/1926.cpp)                                            |
 |  1930  |   Medium   | [Unique Length-3 Palindromic Subsequences](Problems/1930.cpp)                                      |
 |  1934  |   Medium   | [Confirmation Rate](Problems/1934.cpp)                                                             |
+|  1943  |   Medium   | [Describe the Painting](Problems/1943.cpp)                                                         |
 |  1947  |   Medium   | [Maximum Compatibility Score Sum](Problems/1947.cpp)                                               |
 |  1954  |   Medium   | [Minimum Garden Perimeter to Collect Enough Apples](Problems/1954.cpp)                             |
 |  1962  |   Medium   | [Remove Stones to Minimize the Total](Problems/1962.cpp)                                           |