P1440 求m区间内的最小值

TLE #2 #10

和题解没有多大区别啊。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2*1e6+10;
int n,m,ans[MAXN];
struct node{
	int val;
	int pos;
}a[MAXN];
deque<node> q;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		a[i].val=read();
		a[i].pos=i-1;
	}
	ans[0]=0;
	for(int i=1;i<n;i++)
	{
		while(!q.empty()&&q.back().val>=a[i].val)
			q.pop_back();
		q.push_back(a[i]);
		while(!q.empty()&&q.front().pos<i-m)
			q.pop_front();
		ans[i]=q.front().val;
	}
	for(int i=0;i<n;i++)
		cout<<ans[i]<<endl;
	return 0;
}