关于STL和pb_ds的优先队列

P1440 求m区间内的最小值

Windows_Update @ 2022-10-20 09:25:33

RT,本题不能用STL优先队列过,想尝试pb_ds的优先队列,
但是在将STL的优先队列更换为pb_ds的优先队列后原来TLE的点(#7)会RE:Runtime Error. Received signal 11: Segmentation fault with invalid memory reference.

本萌新想知道为什么qwq(用单调队列AC了就是想问问)

code:

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
template <typename Tp>
inline void read(Tp &x){
    x=0;
    int f(1);
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return;
}
void print(long long x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+48);
    return;
}
int n,m,tmp;
struct node{
    int val,num;
    bool operator<(const node &x)const{
        return val>x.val;
    }
};
__gnu_pbds::priority_queue<node>q;//只替换命名空间其他一样
int main(){
    #ifndef ONLINE_JUDGE
    freopen("one.in","r",stdin),freopen("one.out","w",stdout);
    #endif
    read(n),read(m);
    for(int i=1;i<=n;++i){
        read(tmp);
        if(i==1)print(0),putchar('\n');
        else if(!q.empty())
            print(q.top().val),putchar('\n');
        if(!q.empty())
            while(q.top().num<=i-m)q.pop();
        q.push({tmp,i});
    }
    return 0;
}

by 东灯 @ 2022-10-20 11:35:16

因为你写空 pop 了,虽然我不知道哪写了,但是写了

std::pqpop 不会出事,但是 pbdspq 会 RE。


|