| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贪心+树状数组#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;
}
void add(int x)
{
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;
add(j);
tmp--;
}
}
printf("%d\n",sum(N));
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator