leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2751.cpp (1165B)

      1 class Solution {
      2   public:
      3     vector<int> survivedRobotsHealths(const vector<int> &positions, vector<int> &healths,
      4                                       const string &directions) const {
      5         static int indexes[100001];
      6         const int n = size(positions);
      7         vector<int> res;
      8         stack<int> st;
      9 
     10         iota(indexes, indexes + n, 0);
     11         sort(indexes, indexes + n, [&](int a, int b) { return positions[a] < positions[b]; });
     12 
     13         for (const int idx : std::span(indexes, n)) {
     14             if (directions[idx] == 'R') {
     15                 st.push(idx);
     16                 continue;
     17             }
     18 
     19             int &health = healths[idx];
     20             while (!st.empty() && health > 0) {
     21                 int &top = healths[st.top()];
     22                 if (health == top)
     23                     top = health = 0, st.pop();
     24                 else if (health > top)
     25                     health--, top = 0, st.pop();
     26                 else
     27                     top--, health = 0;
     28             }
     29         }
     30 
     31         for (int i = 0; i < n; i++) {
     32             if (healths[i] == 0) continue;
     33             res.push_back(healths[i]);
     34         }
     35 
     36         return res;
     37     }
     38 };