Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贪心+树状数组

Posted by 322019281 at 2018-12-31 11:01:52 on Problem 1201
```#include<cstdio>
using namespace std;

const int N=50001;
int a[N],b[N],c[N],t[N+1];
bool v[N+1];

void qsort(int l,int r)
{
int i=l,j=r,k=b[l+r>>1],tmp;
while(i<=j)
{
while(b[i]<k)i++;
while(b[j]>k)j--;
if(i<=j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
tmp=b[i];
b[i]=b[j];
b[j]=tmp;
tmp=c[i];
c[i]=c[j];
c[j]=tmp;
i++;
j--;
}
}
if(i<r)qsort(i,r);
if(l<j)qsort(l,j);
}

int sum(int x)
{
int res=0;
while(x)
{
res+=t[x];
x-=x&-x;
}
return res;
}

{
while(x<=N)
{
t[x]++;
x+=x&-x;
}
}

int main()
{
int n,i,j,tmp;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
b[i]++;
}
qsort(1,n);
for(i=1;i<=n;i++)
{
tmp=c[i]-(sum(b[i])-sum(a[i]));
j=b[i];
while(tmp>0)
{
while(v[j])j--;
v[j]=true;
tmp--;
}
}
printf("%d\n",sum(N));
return 0;
}```

Followed by: