π酱 @ 2018-08-21 17:50:24
#include<bits/stdc++.h>
using namespace std;
struct Node{
int Data,Address;
}Maxn[1000010],Minn[1000010];
Node x,k;
int n,m,Front_Max,Back_Max,Front_Min,Back_Min,Ans_Max[1000100],Ans_Min[1000100];
template <typename T>
int Read(T &x) {
x=0;
int f=1;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=-f;
for(; isdigit(c); c=getchar()) x=x*10+c-'0';
x*=f;
if(c=='\n')return 1;
else return 0;
}
void Write(long long x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
Write((x-x%10)/10);
}
putchar(x%10+'0');
}
int main(){
Read(n);
Read(m);
Front_Max=Back_Max=Front_Min=Front_Min=1;
for(int i=1;i<m;i++){
Read(x.Data);
x.Address=i;
while((Maxn[Front_Max].Data<=x.Data)&&(Front_Max<=Back_Max))
Back_Max--;
Maxn[++Back_Max]=x;
while((Minn[Front_Min].Data>=x.Data)&&(Front_Min<=Back_Min))
Back_Min--;
Minn[++Back_Min]=x;
}
for(int i=m;i<=n;i++){
Read(x.Data);
x.Address=i;
while((Maxn[Back_Max].Data<=x.Data)&&(Front_Max<=Back_Max))
Back_Max--;
Maxn[++Back_Max]=x;
while((Minn[Back_Min].Data>=x.Data)&&(Front_Min<=Back_Min))
Back_Min--;
Minn[++Back_Min]=x;
while((Maxn[Front_Max].Address<=i-m)&&(Front_Max<=Back_Max))
Front_Max++;
while((Minn[Front_Min].Address<=i-m)&&(Front_Min<=Back_Min))
Front_Min++;
Ans_Max[i-m]=Maxn[Front_Max].Data;
Ans_Min[i-m]=Minn[Front_Min].Data;
}
for(int i=0;i<n-m;i++){
Write(Ans_Min[i]);
putchar(' ');
}
Write(Ans_Min[n-m]);
putchar('\n');
for(int i=0;i<n-m;i++){
Write(Ans_Max[i]);
putchar(' ');
}
Write(Ans_Max[n-m]);
putchar('\n');
return 0;
}
by 外太空 @ 2018-08-21 18:00:12
你的昵称太狂了
by WA鸭鸭 @ 2018-08-21 18:45:44
因为我在
by KJGKMTZB @ 2018-08-22 20:13:25
您怕是一个数学神犇吧