算法
(imos法) $O(N\log N)$
本题和 ABC183D 的解法一致,但这里的值域比较大,我们可以用 std::map
来维护
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
int main() {
int n;
cin >> n;
map<int, int> mp;
rep(i, n) {
int a, b;
cin >> a >> b;
mp[a]++;
mp[a + b]--;
}
int pre = -1, now = 0;
vector<int> ans(n + 1);
for (auto [t, x] : mp) {
ans[now] += t - pre;
now += x;
pre = t;
}
for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
return 0;
}