leetcode

commit 20d5f52949381ac4f7ec635b5a2906809137144f
parent ccdc06381d6b8aed72122ef14d92cbb0b21e908b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 13 Jul 2024 15:43:14 +0200

Daily Problem

Diffstat:
A
Problems/2751.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/2751.cpp b/Problems/2751.cpp
@@ -0,0 +1,38 @@
+class Solution {
+  public:
+    vector<int> survivedRobotsHealths(const vector<int> &positions, vector<int> &healths,
+                                      const string &directions) const {
+        static int indexes[100001];
+        const int n = size(positions);
+        vector<int> res;
+        stack<int> st;
+
+        iota(indexes, indexes + n, 0);
+        sort(indexes, indexes + n, [&](int a, int b) { return positions[a] < positions[b]; });
+
+        for (const int idx : std::span(indexes, n)) {
+            if (directions[idx] == 'R') {
+                st.push(idx);
+                continue;
+            }
+
+            int &health = healths[idx];
+            while (!st.empty() && health > 0) {
+                int &top = healths[st.top()];
+                if (health == top)
+                    top = health = 0, st.pop();
+                else if (health > top)
+                    health--, top = 0, st.pop();
+                else
+                    top--, health = 0;
+            }
+        }
+
+        for (int i = 0; i < n; i++) {
+            if (healths[i] == 0) continue;
+            res.push_back(healths[i]);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1240,6 +1240,7 @@ for solving problems.
 |  2740  |   Medium   | [Find the Value of the Partition](Problems/2740.cpp)                                               |
 |  2742  |    Hard    | [Painting the Walls](Problems/2742.cpp)                                                            |
 |  2745  |   Medium   | [Construct the Longest New String](Problems/2745.cpp)                                              |
+|  2751  |    Hard    | [Robot Collisions](Problems/2751.cpp)                                                              |
 |  2766  |   Medium   | [Relocate Marbles](Problems/2766.cpp)                                                              |
 |  2767  |   Medium   | [Partition String Into Minimum Beautiful Substrings](Problems/2767.cpp)                            |
 |  2780  |   Medium   | [Minimum Index of a Valid Split](Problems/2780.cpp)                                                |