比赛 20120413 评测结果 AAEEEEEEEEEA
题目名称 工作进度 最终得分 25
用户昵称 Oo湼鞶oO 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-13 20:28:22
显示代码纯文本
#include <cstdio>
#include <cstdlib>

#define I_F "joba.in"
#define O_F "joba.out"

const int Maxn=100000+1;
const short P=20;

struct str
{
	long d,p;
}s[Maxn], *h[Maxn]={NULL};
int n,tail=1;
long long ans=0;

void Input();
template<typename Any>
inline void Swap(Any&, Any&);
void Sort(const int&, const int&);
void Insert(const int&);
void Delete();
void Search();
void Output();

int main()
{
	Input();
	Sort(1,n);
	Search();
	Output();
	return 0;
}

void Input()
{
	s[0].d=s[0].p=0;
	freopen(I_F,"r",stdin);
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%ld%ld",&s[i].d,&s[i].p);
}

template<typename Any>
inline void Swap(Any &a, Any &b)
{
	Any t=a;
	a=b;
	b=t;
}

void Sort(const int &l, const int &r)
{
	if (r-l>P)
	{
		long x=s[l+rand()%(r-l+1)].d;
		int i=l, j=r;
		do
		{
			while (s[i].d<x) ++i;
			while (s[j].d>x) ++j;
			if (i<=j)
				Swap(s[i++],s[j--]);
		} while (i<j);
		if (i<r) Sort(i,r);
		if (l<j) Sort(l,j);
	}
	else
	{
		bool f=true;
		for (int i=l; i<r && f; i++)
		{
			f=false;
			for (int j=r; j>i; j--)
				if (s[j].d<s[j-1].d)
					Swap(s[j],s[j-1]),
					f=true;
		}
	}
}

void Insert(const int &x)
{
	h[tail++]=&s[x];
	for (int t=tail-1; t>1 && h[t]->p>h[t/2]->p; t/=2)
		Swap(h[t],h[t/2]);
}

void Delete()
{
	h[1]=h[--tail];
	int t=1;
	for (bool f=true; f;)
		if (t*2>=tail)
			f=false;
		else
			if (t*2+1>=tail)
				if (h[t]->p<h[t*2]->p)
				{
					Swap(h[t],h[t*2]);
					t*=2;
				}
				else
					f=false;
			else
				if (h[t*2]->p>h[t*2+1]->p)
					if (h[t]<h[t*2])
					{
						Swap(h[t],h[t*2]);
						t*=2;
					}
					else
						f=false;
				else
					if (h[t]<h[t*2+1])
					{
						Swap(h[t],h[t*2+1]);
						t=t*2+1;
					}
					else
						f=false;
}

void Search()
{
	int b, a=n;
	do
	{
		b=a;
		Insert(b);
		for (a=b-1; s[a].d==s[b].d; a--)
			Insert(a);
		for (int i=s[a].d; i<s[b].d; i++)
		{
			ans+=h[1]->p;
			Delete();
		}
	} while (a>0);
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%lld\n",ans);
}