#include <cstdlib>
#define N 500010
int queue[N],high[N],d[N];
int n,h,t,ans=0;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&high[i]);
h=0;
t=0;
for (int i=1;i<=n;++i)
{
while (t&&high[queue[t]]<high[i]) ans+=d[t--];
if (t&&high[queue[t]]==high[i])
{
ans+=d[t];
++d[t];
if (t>1) ++ans;
}
else
{
if (t) ++ans;
queue[++t]=i;
d[t]=1;
}
}
printf("%d\n",ans);
return 0;
}
题目:诺诺的队列
状态: Unaccepted
测评机： Xeond[6]
得分： 90分
提交日期： 2012-12-9 11:11:00
有效耗时： 891毫秒
测试结果1: 通过本测试点|有效耗时141ms
测试结果2: 通过本测试点|有效耗时46ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时78ms
测试结果5: 通过本测试点|有效耗时63ms
测试结果6: 通过本测试点|有效耗时78ms
测试结果7: 通过本测试点|有效耗时63ms
测试结果8: 通过本测试点|有效耗时281ms
测试结果9: 通过本测试点|有效耗时94ms
测试结果10: 选手程序运行超过时限
这是什么情况……500000的数据O（n）超时？
另：NOI2010海拔情况同上求拯救……
#include <stdio.h>
int queue[500010],high[500010],d[500010];
int n,t,ans=0;
int main()
{
int i;
scanf("%d\n",&n);
queue[0]=0;
high[0]=100000;
for (i=1;i<=n;++i) scanf("%d",&high[i]);
t=0;
for (i=1;i<=n;++i)
{
while (high[queue[t]]<high[i]) ans+=d[t--];
if (high[queue[t]]==high[i])
if (t>1) ans+=++d[t]; else ans+=d[t]++;
else
{
if (t) ++ans;
queue[++t]=i;
d[t]=1;
}
}
printf("%d\n",ans);
return 0;
}