AtCoder Beginner Contest 221 D - Online games

题目描述

Sample Input

3
1 2
2 3
3 1

Sample Output

Copy
2 2 0

题目大意

先输入数字N，代表有N个注册者，然后接下来有N行，每一行有两个数字$A_i,B_i$，$A_i$代表第$i$个使用者的第一次登录的时间，$B_i$代表第$i$个使用者连续登录的天数。输出有N个数字，第k个数字代表第k天有多少个使用者登录。
其实也就是给定n条线段，$[l_i,r_i]$。对于每个k值，输出每个k值被多少条线段覆盖。

实现思路

假如说我们现在平面上有n条线段，然后我们有一个标记竖线record从左到右扫描

• 每次遇到线段的左端点，record+1
• 每次遇到线段的右端点，record-1
• record的值就是当前k位置的结果了

但是有一种特殊的情况，假如说以最左的点为左端点的线段有多条，那么我们上面的做法就会导致结果错误，大家可以在纸上模拟一下。所以我们需要特判

• 当多个相同的左端点是最左边的点时，我们要更新一下答案
• 不是最左边的点，就不需要更新答案。

完整代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{ll n;cin >> n;vector<pair<ll, ll>> vt;ll a, b;for (int i = 0; i < n; i++){cin >> a >> b;vt.push_back(make_pair(a, 1));vt.push_back(make_pair(a + b, -1));}int now = 0;int p = 0;int ans[n + 1];memset(ans, 0, sizeof(ans));sort(vt.begin(), vt.end());int len = vt.size();for (int i = 0; i < len; i++){if (i > 0 && vt[i].first != vt[i - 1].first)ans[now] += vt[i].first - p;p = vt[i].first;now += vt[i].second;}for (int i = 1; i <= n; i++){cout << ans[i] << " ";}cout << endl;
}

题目链接