Submission #51444473

---

Source Code Expand

// LUOGU_RID: 151664947
// Author: gsczl71
// Copyright (c) 2024 gsczl71 All rights reserved.
// Problem: D - Online games
// Contest: AtCoder - AtCoder Beginner Contest 221
// URL: https://atcoder.jp/contests/abc221/tasks/abc221_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2024-03-19 16:33:42

// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define x0 _x0_
#define y1 _y1_
#define endl '\n'
#define re register
#define pb push_back
#define vi vector<int>
#define pq priority_queue
#define mem(a,x) memset((a),(x),sizeof(a))
#define debug puts("AK IOI")
#define sz(s) (int)(s.size())
#define all(a) a.begin(),a.end()
#define rd(l,r) (myrand()%(r-l+1)+l)
#define print(x) {cout<<x<<endl;return;}
#define ctn(e) if(e) continue
#define brk(e) if(e) break
#define rt(e) if(e) return
#define ll_(e) (1ll*(e))
#define For(x,y,z) for(int x = y;x <= z;x++)
#define For_(x,y,z) for(int x = y;x <= z;x--)
using namespace std;
#define int long long
const int mod = 1e9+7;
//const int mod = 998244353;
mt19937 myrand(time(0));
const int inf = 0x3f3f3f3f,N = 2e5+5,M = 1e6+5,K = 3000+5;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N],b[N];
int d[N];
void solve(){
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i] >> b[i];
	vector<pii> v;
	for(int i =1;i<=n;i++){
		v.pb({a[i],1});
		v.pb({a[i]+b[i],-1});
	}sort(all(v));
	for(int i = 1;i < sz(v);i++) v[i].sc += v[i-1].sc;
	for(int i = 0;i + 1 < sz(v);i++){
		d[v[i].sc] += v[i+1].fs-v[i].fs;
	}for(int i =1;i <= n;i++){
		cout<<d[i]<<" ";
	}
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	For(_,1,T) solve();
	return 0;
}

Submission Info

Judge Result