C. Covered Points Count
题目大意:有n条线段,问有多少个点被i条线段覆盖(i=1~n)。
很常见的线段覆盖套路题QAQ。
坐标排序后把左端点当做+1,右端点当做-1,扫一遍统计答案即可。
但是记得开ll,数组大小开双倍。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%lld ",a)
using namespace std;
int n,tot;
ll ans[200050];
ll l,r,now=0;
ll read()
{
ll s=0,t=1; char c;
while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
return s*t;
}
struct dist
{
ll num,h;
}a[400050];
bool cmp(dist a,dist b)
{
return a.num==b.num?a.h<b.h:a.num<b.num;
}
int main()
{
n=read(); now=0;
for (int i=1;i<=n;i++) {
l=read(),r=read();
a[++tot].num=l,a[tot].h=1;
a[++tot].num=r+1,a[tot].h=-1;
}
sort(a+1,a+tot+1,cmp);
for (int i=1;i<=tot;i++) {
ans[now]+=a[i].num-a[i-1].num;
now+=a[i].h;
}
for (int i=1;i<=n;i++)
out(ans[i]);
return 0;
}
