我惠美如画 @ 2018-12-22 20:35:57

by 我惠美如画 @ 2018-12-22 20:37:30

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<deque>
using namespace std;
int a[1000006],b[1000006];int sum1=0,sum2=0;
deque<int> q,m;
int main()
{
    ios::sync_with_stdio(false);
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=x;i++)
    cin>>a[i],b[i]=a[i];
    for(int i=1;i<=x;i++)
    {
        sum2++;
        for(int j=1;j<=x;j++)
        {
            while(!m.empty()&&b[m.back()]>b[i])
                m.pop_back();
            while(!m.empty()&&(i-m.front())>=y)
                m.pop_front();
            m.push_back(i);
        }
        if(sum2>=y)
        cout<<b[m.front()]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=x;i++)
    {
        sum1++;
        for(int j=1;j<=x;j++)
        {
            while(!q.empty()&&a[q.back()]<a[i])
                q.pop_back();
            while(!q.empty()&&(i-q.front())>=y)
                q.pop_front();
            q.push_back(i);
        }
        if(sum1>=y)
        cout<<a[q.front()]<<" ";
    }
    return 0;
}

非常抱歉0.0

by encore @ 2018-12-22 21:09:52

算法上已经很优了，常数的话在oj上没用。真的要优化常数加register，读优，i++改++i，手写STL之类

by encore @ 2018-12-22 21:23:12

@encore 等等这是手工模拟啊

by encore @ 2018-12-22 21:23:38

@encore 老花了，还以为是单调队。。。

by encore @ 2018-12-22 21:24:12

@我惠美如画 你用单调队列试试看

by 我惠美如画 @ 2018-12-22 21:25:27

@encore 老哥，我表示不会用单调队列QWQ

by encore @ 2018-12-22 21:41:05

@我惠美如画 那就ST