TIOJ 1168 進階的入門

http://tioj.infor.org/problems/1168

因為操作都是對於最大跟最小 所以就放兩個priority queue
然後因為怕重複對一個東東操作太多次 所以再記錄一下有沒有重複就好

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<bits/stdc++.h> #include"lib1168.h" using namespace std; struct node{ int v,st; node(int v,int st){ this->v=v; this->st=st; } friend bool operator < (const node &l,const node &r){ return l.v<r.v; } friend bool operator > (const node &l,const node &r){ return l.v>r.v; } }; priority_queue<node,vector<node>,greater<node> > pqg; priority_queue<node,vector<node>, less<node> > pql; int sz,cnt; bool ped[1000006]; inline void chk(){ if(!sz){ while(pql.size())pql.pop(); while(pqg.size())pqg.pop(); } else{ while(ped[pqg.top().st])pqg.pop(); while(ped[pql.top().st])pql.pop(); } } void pop_big(){ chk(); ped[pql.top().st]=1; pql.pop(); sz--; } void pop_small(){ chk(); ped[pqg.top().st]=1; pqg.pop(); sz--; } void push(int s){ chk(); pqg.push({s,cnt}); pql.push({s,cnt}); cnt++; sz++; } int big(){ chk(); return pql.top().v; } int small(){ chk(); return pqg.top().v; }