BZOJ 2276 Temperature

two-pointer型单调队列。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000050
using namespace std;
int n,l[maxn],r[maxn],q[maxn],h=,t=,ans=;
int read()
{
char ch;int data=,f=;
while (ch<'' || ch>'')
{
if (ch=='-') f=-;
ch=getchar();
}
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data*f;
}
int main()
{
n=read();
for (int i=;i<=n;i++) l[i]=read(),r[i]=read();
ans=;q[++t]=;
for (int i=;i<=n;i++)
{
while ((h<=t) && (l[i]>=l[q[t]])) t--;
q[++t]=i;
while ((h<=t) && (l[q[h]]>r[i])) h++;
ans=max(ans,i-q[h-]);
}
printf("%d\n",ans);
return ;
}
上一篇:基本数据类型float和double的区别


下一篇:CentOS7安装vncserver(启动失败及连接黑屏解决办法)