比赛 |
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);
}