xeri_chen @ 2019-06-10 21:52:33
#include<bits/stdc++.h>
#define N 2000001
using namespace std;
deque <int> dq;
deque <int> dq2;
int a[N],k,d[N],top;
void tj2(int x)
{
while(!dq2.empty()&&a[dq2.back()]>a[x])
{
dq2.pop_back();
}
while(!dq2.empty()&&x-dq2.front()>=k)
{
dq2.pop_front();
}
dq2.push_back(x);
}
void tj(int x)
{
while(!dq.empty()&&a[dq.back()]<a[x])
{
dq.pop_back();
}
while(!dq.empty()&&x-dq.front()>=k)
{
dq.pop_front();
}
dq.push_back(x);
}
int main()
{
int n;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
tj(i);
tj2(i);
if(i>=k-1)
{
cout<<a[dq2.front()]<<" ";
d[top++]=a[dq.front()];
}
}
cout<<endl;
for(int i=0;i<top;i++)
cout<<d[i]<<" ";
return 0;
}
by 梧桐灯 @ 2019-06-10 21:56:16
吸口氧气试试
by 梧桐灯 @ 2019-06-10 21:56:29
吸口氧气试试
by Celestial_Scarlet @ 2019-06-10 21:57:37
cin cout的锅别甩给STL
by xeri_chen @ 2019-06-10 21:59:08
@baoyu 是因为cin和cout要慢一点吗??
by wxwoo @ 2019-06-10 22:01:05
因为有人写的ST表和线段树(
by xeri_chen @ 2019-06-10 22:01:59
@wxwoo 用单调队列不是应该要快一点吗
by 梧桐灯 @ 2019-06-10 22:02:27
@xeri_chen 真的cin&cout很慢,不信你可以试一试,比如读入个一百万个int型的
by wxwoo @ 2019-06-10 22:02:29
@xeri_chen 单调队列确实快啊
by wxwoo @ 2019-06-10 22:02:59
但你cin/cout光读入就超时了
by Celestial_Scarlet @ 2019-06-10 22:03:20
@xeri_chen 1e6的IO量 cin cout就别想过了(