A bit encouraging, a bit discouraging, that's micro-encouragement. After receiving micro-encouragement, a person will stand up if they were originally squatting, and squat down if they were originally standing. Now, there is a line of people standing in a row, and you can apply micro-encouragement to a range of people. People in that range who were originally squatting will stand up, and those who were originally standing will squat down. In the beginning, everyone is standing, and after several rounds of encouragement, you're asked how many people are still standing.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains an integer N (N ≤ 2,000,000,000), representing N people arranged in a row from left to right, with the person at the far left numbered 1, the next person numbered 2, and so on, up to N. The second line contains an integer M (M ≤ 100000), indicating the number of micro-encouragements to follow. The next M lines each contain two integers Li and Ri, indicating a micro-encouragement to be applied to the closed interval from Li to Ri, inclusive. | Please output the number of people standing at the end. |
| 5 3 1 3 3 5 1 5 | 4 |
Thought Process
Use a Map to store the range of each micro-encouragement because after being encouraged twice, a person will return to their original state, which is standing.
After R+1, we can know that R-L is the number of people who have been slightly encouraged. Put L and R into the Map. If there is already data, it means there is a duplicate slight encouragement. So delete the Map values that have already appeared, and then save the data that hasn't been saved to the Map.
Finally, convert the Map to Vector<Pair>, then perform the R-L action in pairs and add the answers together.
Sample Code－ZeroJudge B526: Little Encouragement
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<int, int>MAP;
void change(int N)
{
if (MAP[N] == 0)
{
MAP[N]++;
return;
}
MAP.erase(N);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 0; i<M; i++)
{
int a, b;
cin >> a >> b;
b++;
change(a);
change(b);
}
vector<pair<int, int>>ans;
copy(MAP.begin(), MAP.end(), back_inserter(ans));
int sum = 0;
for (int i = 0; i<ans.size(); i++)
{
sum += ans[i+1].first - ans[i].first;
i++;
}
cout << N-sum << "\n";
}
//ZeroJudge B526
//Dr. SeanXD