あるプレイヤーがログインし始めた日あるいはログインしなくなった日, すなわちある \(i\) が存在して \(X=A_i\) または \(X=A_i+B_i\) をみたす \(X\) を昇順に\(X_1\) , \(X_2\) , \(\ldots\) , \(X_K\) とします。
このとき、\(X_i\leq Y \leq X_{i+1}-1\) をみたす \(Y\) について、\(Y\) 日目にログインした人数は一定となります。 また、\(Y<X_1\) または \(X_K\leq Y\) をみたす\(Y\) については \(Y\) 日目にログインした人数は \(0\) 人なので考える必要はないです。よって、カウンターと、答えとなる配列を用意し、最初カウンターと配列を \(0\) に初期化した上で、\(i=1,2,\ldots,K-1\) について次のようにすれば良い事が分かります。

• \(X_i\) 日目にログインし始めた人の数だけカウンターを増やし、ログインしなくなった人の数だけカウンターを減らす。
• この時点でのカウンターの数字を \(C\) とし、\(C\) 人だけログインした日数を\(X_{i+1}-X_i\) だけ増加させる。

計算量は最初の \(\{ X_i\} \) のソートに \(O(N\log N)\) かかり, その後の操作は \(O(N)\) で出来るため, 全体で \(O(N\log N)\) である事が分かります。よって、この問題を十分高速に解く事が出来ました。

c++による実装例 :

#include <bits/stdc++.h>
using namespace std;

#define N 200010
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n;
	int a, b;
	vector<pair<int, int> >x;
	int cnt;
	int ans[N];
	rep(i, N)ans[i] = 0;

	cin >> n;
	rep(i, n) {
		cin >> a >> b;
		x.push_back({ a,1 });
		x.push_back({ a + b,-1 });
	}

	sort(x.begin(), x.end());

	cnt = 0;
	rep(i, (x.size())-1) {
		cnt += x[i].second;
		ans[cnt] += ((x[i + 1].first) - (x[i].first));
	}

	rep(i, n - 1)cout << ans[i + 1] << " ";
	cout << ans[n] << endl;

	return 0;
}