为什么都是STLdeque,我却TLE了两个点,蒟蒻求救

P1886 滑动窗口 /【模板】单调队列

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就别想过了(


| 下一页