QBHEAP spoj – Hàng đợi có độ ưu tiên

#include <bits/stdc++.h> using namespace std; int n; vector<int> a; void DownHeap(int p) { int key=a[p]; while(p*2<=n) { int c=p*2; if(c<n && a[c]<a[c+1]) c++; if(a[c]<=key) break; a[p]=a[c]; p=c; } a[p]=key; } void UpHeap(int c) { int key=a[c]; while(c>=2) { int p=c/2; if(a[p]>=key) break; a[c]=a[p]; c=p; } a[c]=key; } void AddHeap(int val) { n++; a[n]=val; UpHeap(n); } void RemoveHeap() { a[1]=a[n]; n--; DownHeap(1); } void Init() { a.resize(15000+100); } void Solve() { char s; int tg; while (scanf("%c",&s) != EOF) { if(s=='+') { scanf("%d",&tg); if(n<15000) AddHeap(tg); } if(s=='-') { if(n>0) tg=a[1]; while(n>0 && tg==a[1]) RemoveHeap(); } } vector<int> b; while(n) { tg=a[1]; if( b.empty() || tg!=b.back()) b.push_back(tg); RemoveHeap(); } cout<<b.size()<<endl; for (int i=0;i<b.size();i++) cout<<b[i]<<endl; } int main() { Init(); Solve(); }

#include <bits/stdc++.h> #include <queue> using namespace std; priority_queue <long, vector<long>, less_equal<long> > heap; long tmp; vector <long> res; string c; int main() { while (cin >> c) { if (c[0]=='+') { c.erase(0,1); tmp = atoi(c.c_str()); if (heap.size()<15000) heap.push(tmp); } else if (c[0]=='-') { if (!heap.empty()) { tmp = heap.top(); while (!heap.empty() && heap.top()==tmp) heap.pop(); } } else break; } while (!heap.empty()) { tmp = heap.top(); while (!heap.empty() && heap.top()==tmp) heap.pop(); res.push_back(tmp); } cout << res.size()<<endl; for (unsigned i=0; i<res.size(); i++) cout << res[i] << endl; return 0; }

const fi='; nmax=15001; type data=longint; var f:text; Heap,B:array[0..nmax+1] of data; nHeap,n:data; procedure swap(a,b:data); var z:data; begin z:=heap[a]; heap[a]:=heap[b]; heap[b]:=z; end; procedure UpHeap(i:data); begin if (i=1) or (heap[i]<=heap[i div 2]) then exit; swap(i,i div 2); upheap(i div 2); end; procedure push(x:data); begin inc(nHeap); heap[nHeap]:=x; upheap(nHeap); end; procedure downheap(i:data); var j:data; begin j:=i*2; if j>nHeap then exit; if (j<nHeap) and (heap[j+1]>heap[j]) then inc(j); if heap[i]>=heap[j] then exit; swap(i,j); downheap(j); end; procedure pop; begin heap[1]:=heap[nHeap]; dec(nHeap); downheap(1); end; procedure xuli; var i,j,x,tmp,res:data; c:char; begin assign(f,fi); reset(f); nheap:=0; while not seekeof(f) do begin read(f,c); if c='+' then begin readln(f,x); if nHeap<15000 then begin push(x); end; end else begin readln(f); if nHeap>0 then begin tmp:=heap[1]; while (nheap>0) and (heap[1]=tmp) do pop; end; end; end; res:=0; while nHeap>0 do begin tmp:=heap[1]; while (nHeap>0) and (heap[1]=tmp) do pop; inc(res); b[res]:=tmp; end; writeln(res); for i:=1 to res do writeln(b[i]); close(f); end; begin xuli; end.