单调队列+快读80分,2、10TLE了,求助!!!

P1440 求m区间内的最小值

sczh @ 2020-01-18 12:08:26

#include<bits/stdc++.h>
#define gc getchar()
#define MX 2000005
#define ep empty()
using namespace std;
int m,ans[MX];struct Node{int num,x;};deque<Node>d;
void q_in(int &x){
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+c-48;c=gc;}
}
Node pack(int _num,int _x){
    Node a;a.x=_x;a.num=_num;return a;
}
void deque_push(int _num,int _x){
    if(!d.ep&&_num-d.front().num+1>m)d.pop_front();
    while(!d.ep&&d.back().x>=_x)d.pop_back();
    d.push_back(pack(_num,_x));
    ans[_num+1]=d.front().x;
}
int main(){
    int n;q_in(n);q_in(m);
    for(int i=1;i<=n;i++){int q;q_in(q);deque_push(i,q);}
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}

by 万弘 @ 2020-01-18 12:40:20

@编程boy deque常数太大,请手写队列


by hly1204 @ 2020-01-18 12:44:07

这题线段树都能过好像


by 是真的囬气 @ 2020-01-18 18:43:17


cin和cout过不去,必须用scanf和printf

|