Submission #26328261

---

Source Code Expand

#include<bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)

using namespace std;

const int N=6e5+5;

int n,ans[N];
pair<int,int> a[N];
int tmp[N],tot;
int tr[N<<2],tag[N<<2];
int d[N];

void pushdown(int rt,int l,int r)
{
	if(!tag[rt]) return;
	tag[lson]+=tag[rt],tag[rson]+=tag[rt];
	tr[lson]+=tag[rt]*(mid-l+1);
	tr[rson]+=tag[rt]*(r-mid);
	tag[rt]=0;
}
void pushup(int rt)
{
	tr[rt]=tr[lson]+tr[rson];
}
void update(int rt,int l,int r,int L,int R)
{
	if(L<=l&&r<=R){
		tr[rt]+=r-l+1;
		tag[rt]+=1;
		return;
	}
	pushdown(rt,l,r);
	if(L<=mid) update(lson,l,mid,L,R);
	if(R>mid) update(rson,mid+1,r,L,R);
	pushup(rt);
}
int ask(int rt,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[rt];
	pushdown(rt,l,r);
	int res=0;
	if(L<=mid) res+=ask(lson,l,mid,L,R);
	if(R>mid) res+=ask(rson,mid+1,r,L,R);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);

	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i].first>>a[i].second;
		a[i].second=a[i].first+a[i].second;
	}
	for(int i=1;i<=n;++i){
		tmp[++tot]=a[i].first;
		tmp[++tot]=a[i].second;
	}
	sort(tmp+1,tmp+tot+1);
	tot=unique(tmp+1,tmp+tot+1)-tmp-1;
	for(int i=1;i<=n;++i){
		a[i].first=lower_bound(tmp+1,tmp+tot+1,a[i].first)-tmp;
		a[i].second=lower_bound(tmp+1,tmp+tot+1,a[i].second)-tmp;
	}

	for(int i=1;i<=n;++i){
		update(1,1,tot,a[i].first,a[i].second-1);
	}
	for(int i=1;i<tot;++i){
		int now=ask(1,1,tot,i,i);
		ans[now]+=(tmp[i+1]-tmp[i]);
	}
	
	for(int i=1;i<=n;++i){
		cout<<ans[i]<<" ";
	}
	return 0;
}

Submission Info

Judge Result