<p>There are <code>n</code> <strong>1-indexed</strong> robots, each having a position on a line, health, and movement direction.</p>

<p>You are given <strong>0-indexed</strong> integer arrays <code>positions</code>, <code>healths</code>, and a string <code>directions</code> (<code>directions[i]</code> is either <strong>&#39;L&#39;</strong> for <strong>left</strong> or <strong>&#39;R&#39;</strong> for <strong>right</strong>). All integers in <code>positions</code> are <strong>unique</strong>.</p>

<p>All robots start moving on the line<strong> simultaneously</strong> at the <strong>same speed </strong>in their given directions. If two robots ever share the same position while moving, they will <strong>collide</strong>.</p>

<p>If two robots collide, the robot with <strong>lower health</strong> is <strong>removed</strong> from the line, and the health of the other robot <strong>decreases</strong> <strong>by one</strong>. The surviving robot continues in the <strong>same</strong> direction it was going. If both robots have the <strong>same</strong> health, they are both<strong> </strong>removed from the line.</p>

<p>Your task is to determine the <strong>health</strong> of the robots that survive the collisions, in the same <strong>order </strong>that the robots were given,<strong> </strong>i.e. final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.</p>

<p>Return <em>an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.</em></p>

<p><strong>Note:</strong> The positions may be unsorted.</p>

<div class="notranslate" style="all: initial;">&nbsp;</div>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img height="169" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516011718-12.png" width="808" /></p>

<pre>
<strong>Input:</strong> positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = &quot;RRRRR&quot;
<strong>Output:</strong> [2,17,9,15,10]
<strong>Explanation:</strong> No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img height="176" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.png" width="717" /></p>

<pre>
<strong>Input:</strong> positions = [3,5,2,6], healths = [10,10,15,12], directions = &quot;RLRL&quot;
<strong>Output:</strong> [14]
<strong>Explanation:</strong> There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4&#39;s health is smaller, it gets removed, and robot 3&#39;s health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><img height="172" src="https://assets.leetcode.com/uploads/2023/05/15/image-20230516005114-9.png" width="732" /></p>

<pre>
<strong>Input:</strong> positions = [1,2,5,6], healths = [10,10,11,11], directions = &quot;RLRL&quot;
<strong>Output:</strong> []
<strong>Explanation:</strong> Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= positions.length == healths.length == directions.length == n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= positions[i], healths[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>directions[i] == &#39;L&#39;</code> or <code>directions[i] == &#39;R&#39;</code></li>
	<li>All values in <code>positions</code> are distinct</li>
</ul>

class Solution {
public:
vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
	vector<int>ans;
	set<pair<int, pair<int, int>>> L, R;
	for (int i = 0; i < positions.size(); i++) {
		if (directions[i] == 'L') {
			R.insert(make_pair(positions[i], make_pair(healths[i], i)));
		}
		else {
			L.insert(make_pair(positions[i], make_pair(healths[i], i)));
		}
	}

	auto it = L.end();
	auto limit = L.rbegin().base();
	if (L.size() > 0) {
		it--;
	}
	int cnt = 0;
	while (L.size() != 0 && R.size() != 0) {
		int posL = it->first;
		pair<int, int> p = it->second;
		int healthL = p.first;
		int roboNumberL = p.second;
		auto itR = R.lower_bound(make_pair(posL, make_pair(INT_MIN, INT_MIN)));
		if (itR == R.end()) {
			//db("s", posL);
			if (it == L.begin())
				break;
			it--;
			continue;
		}
		int healthR = itR->second.first;
		int posR = itR->first;
		int roboNumberR = itR->second.second;
		// db("L", itR->second.first, itR->second.second);
		// db("R", it->second.first, it->second.second);
		// ans.push_back(itR->second.first); ans.push_back(itR->second.second);
		// ans.push_back(it->second.first); ans.push_back(it->second.second);

		if (healthL > healthR) {
			R.erase(itR);
			L.erase(it);
			pair<int, pair<int, int>>newL = make_pair(posL, make_pair(healthL - 1, roboNumberL));
			L.insert(newL);
			it = L.lower_bound(newL);
		}
		else if (healthL < healthR) {
			set<pair<int, pair<int, int>>> ::iterator it2 = it;
			// if (it2 == L.end()) {
			// 	ans.push_back(11111);
			// }
			bool Tobreak = false;
			if (it == L.begin()) {
				Tobreak = true;
			}
			if (L.size() != 0)
				it2--;
			// if (it2 == L.end()) {
			// 	ans.push_back(11112);
			// }
			// if (it2 == limit) {
			// 	ans.push_back(11115);
			// }
			L.erase(it);
			R.erase(itR);
			pair<int, pair<int, int>>newR = make_pair(posR, make_pair(healthR - 1, roboNumberR));
			R.insert(newR);
			it = it2;
			if (Tobreak)
				break;
		}
		else {
			set<pair<int, pair<int, int>>> ::iterator it2 = it;
			bool Tobreak = false;
            if (it == L.begin()) {
				Tobreak = true;
			}
			if (L.size() != 0)
				it2--;
			L.erase(it);
			R.erase(itR);
			it = it2;
			if (Tobreak)
				break;
		}
		// if (cnt >= 0) {
		// 	ans.push_back(L.size());
		// 	ans.push_back(R.size());
		// 	if (it == L.end()) {
		// 		ans.push_back(11113);
		// 	}
		// 	print(ans);
		// 	return ans;
		// }
		cnt++;
	}

	map<int, int>mp;
	for (auto x : L) {
		mp[x.second.second] = x.second.first;
	}
	for (auto x : R) {
		mp[x.second.second] = x.second.first;
	}
	for (auto x : mp) {
		ans.push_back(x.second);
	}
	//print(ans);
	return ans;
}
};
265673