Editorial for Double Queue
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; maxn=1000000; var h,g,p,q,a,b:array[0..maxn] of longint; n,m,i,x,y,z:longint; procedure updatemin(x,y:longint); var cha,con:longint; begin if q[x]=0 then begin inc(m); con:=m; end else con:=q[x]; cha:=con shr 1; while (cha>0) and (y<b[cha]) do begin g[con]:=g[cha]; b[con]:=b[cha]; q[g[con]]:=con; con:=cha; cha:=con shr 1; end; g[con]:=x; q[x]:=con; b[con]:=y; end; procedure updatemax(x,y:longint); var cha,con:longint; begin if p[x]=0 then begin inc(n); con:=n; end else con:=p[x]; cha:=con shr 1; while (cha>0) and (y>a[cha]) do begin h[con]:=h[cha]; a[con]:=a[cha]; p[h[con]]:=con; con:=cha; cha:=con shr 1; end; h[con]:=x; p[x]:=con; a[con]:=y; end; procedure editmin(z:longint); var cha,con,x,y:longint; begin x:=g[m]; y:=b[m]; b[m]:=0; g[m]:=0; dec(m); if z>m then exit; cha:=z; con:=z shl 1; while con<=m do begin if (con<m) and (b[con+1]<b[con]) then inc(con); if y<=b[con] then break; g[cha]:=g[con]; b[cha]:=b[con]; q[g[cha]]:=cha; cha:=con; con:=cha shl 1; end; g[cha]:=x; q[x]:=cha; b[cha]:=y; updatemin(x,y); end; procedure editmax(z:longint); var cha,con,x,y:longint; begin x:=h[n]; y:=a[n]; a[n]:=0; h[n]:=0; dec(n); if z>n then exit; cha:=z; con:=z shl 1; while con<=n do begin if (con<n) and (a[con+1]>a[con]) then inc(con); if y>=a[con] then break; h[cha]:=h[con]; a[cha]:=a[con]; p[h[cha]]:=cha; cha:=con; con:=cha shl 1; end; h[cha]:=x; p[x]:=cha; a[cha]:=y; updatemax(x,y); end; begin assign(input,fi); reset(input); m:=0; n:=0; while true do begin read(z); if z=0 then break; if z=1 then begin read(x,y); updatemin(x,y); updatemax(x,y); end else begin if z=2 then begin if n=0 then begin writeln(0); continue; end; x:=h[1]; end else begin if m=0 then begin writeln(0); continue; end; x:=g[1]; end; writeln(x); editmin(q[x]); q[x]:=0; editmax(p[x]); p[x]:=0; end; end; close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<set> using namespace std; typedef pair<int, int> ii; set<ii> memo; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif for(int ctrl; scanf("%d",&ctrl) != EOF && ctrl != 0;) { if(ctrl == 1) { int k, p; scanf("%d%d",&k,&p); memo.insert(ii(p, k)); } else if(memo.empty()) printf("0\n"); else if(ctrl == 2) { printf("%d\n", memo.rbegin()->second); set<ii>::iterator it = memo.end(); memo.erase(--it); } else { printf("%d\n", memo.begin()->second); memo.erase(memo.begin()); } } }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int maxK = 1000006; using namespace std; priority_queue<iii> heap_max; priority_queue<iii, vector<iii>, greater<iii> > heap_min; map<ii, int> M; int cnt[maxK]; int main() { int type, k, p; iii e; scanf("%d", &type); while (type != 0) { if (type == 1) { scanf("%d %d\n", &k, &p); cnt[k]++; heap_min.push(iii(p, ii(k, cnt[k]))); heap_max.push(iii(p, ii(k, cnt[k]))); } if (type == 2) { if (heap_max.size() == 0) {printf("0\n");} else { do { e = heap_max.top(); heap_max.pop(); k = e.Y.X; } while (heap_max.size() && M.count(ii(k, e.Y.Y)) != 0); if (M.count(ii(k, e.Y.Y)) != 0) {printf("0\n");} else { M.insert(pair<ii, int> (ii(k, e.Y.Y), 1)); printf("%d\n", k); } } } if (type == 3) { if (heap_min.size() == 0) {printf("0\n");} else { do { e = heap_min.top(); heap_min.pop(); k = e.Y.X; } while (heap_min.size() && M.count(ii(k, e.Y.Y)) != 0); if (M.count(ii(k, e.Y.Y)) != 0) {printf("0\n");} else { M.insert(pair<ii, int> (ii(k, e.Y.Y), 1)); printf("%d\n", k); } } } scanf("%d", &type); } return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} const FINP=''; FOUT=''; MAXN=1000001; oo=1000000000; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; type heap=object hmin,hmax,inmin,inmax,vmin,vmax:array[1..MAXN] of longint; hminsize,hmaxsize:longint; procedure downMax(i:longint); procedure downMin(i:longint); procedure upMax(i:longint); procedure upMin(i:longint); procedure push(u,k:longint); procedure popMax(var u,k:longint); procedure popMin(var u,k:longint); end; procedure heap.downMax(i:longint); var j:longint; begin j:=i<<1; while (j<=hmaxsize) do begin if (j<hmaxsize) and (hmax[j+1]>hmax[j]) then inc(j); if (hmax[j]>hmax[i]) then begin swap(inmax[inmin[i]],inmax[inmin[j]]); swap(inmin[i],inmin[j]); swap(hmax[i],hmax[j]); swap(vmax[i],vmax[j]); end; i:=j; j:=i<<1; end; end; procedure heap.downMin(i:longint); var j:longint; begin j:=i<<1; while (j<=hminsize) do begin if (j<hminsize) and (hmin[j+1]<hmin[j]) then inc(j); if (hmin[j]<hmin[i]) then begin swap(inmin[inmax[i]],inmin[inmax[j]]); swap(inmax[i],inmax[j]); swap(hmin[i],hmin[j]); swap(vmin[i],vmin[j]); end; i:=j; j:=i<<1; end; end; procedure heap.upMax(i:longint); var j:longint; begin j:=i>>1; while (i>1) and (hmax[i]>hmax[j]) do begin swap(inmax[inmin[i]],inmax[inmin[j]]); swap(inmin[i],inmin[j]); swap(hmax[i],hmax[j]); swap(vmax[i],vmax[j]); i:=j; j:=i>>1; end; end; procedure heap.upMin(i:longint); var j:longint; begin j:=i>>1; while (i>1) and (hmin[i]<hmin[j]) do begin swap(inmin[inmax[i]],inmin[inmax[j]]); swap(inmax[i],inmax[j]); swap(hmin[i],hmin[j]); swap(vmin[i],vmin[j]); i:=j; j:=i>>1; end; end; procedure heap.push(u,k:longint); begin inc(hmaxsize); hmax[hmaxsize]:=u; vmax[hmaxsize]:=k; inc(hminsize); hmin[hminsize]:=u; vmin[hminsize]:=k; inmax[hminsize]:=hmaxsize; inmin[hmaxsize]:=hminsize; upMax(hmaxsize); upMin(hminsize); end; procedure heap.popMax(var u,k:longint); var v:longint; begin u:=hmax[1]; k:=vmax[1]; v:=inmin[1]; hmin[v]:=-maxlongint; upMin(v); swap(hmax[1],hmax[hmaxsize]); swap(vmax[1],vmax[hmaxsize]); swap(inmin[1],inmin[hmaxsize]); inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize; swap(hmin[1],hmin[hminsize]); swap(vmin[1],vmin[hminsize]); swap(inmax[1],inmax[hmaxsize]); inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize; dec(hminsize); downMin(1); dec(hmaxsize); downMax(1); end; procedure heap.popMin(var u,k:longint); var v:longint; begin u:=hmin[1]; k:=vmin[1]; v:=inmax[1]; hmax[v]:=maxlongint; upMax(v); swap(hmax[1],hmax[hmaxsize]); swap(vmax[1],vmax[hmaxsize]); swap(inmin[1],inmin[hmaxsize]); inmax[inmin[1]]:=1; inmax[inmin[hmaxsize]]:=hmaxsize; swap(hmin[1],hmin[hminsize]); swap(vmin[1],vmin[hminsize]); swap(inmax[1],inmax[hminsize]); inmin[inmax[1]]:=1; inmin[inmax[hminsize]]:=hminsize; dec(hminsize); downMin(1); dec(hmaxsize); downMax(1); end; var a:heap; u,k,request:longint; begin // assign(input,'input.txt'); reset(input); // assign(output,'output.txt'); rewrite(output); read(request); while request>0 do begin case request of 1: begin read(k,u); a.push(u,k); end; 2: if a.hmaxsize=0 then writeln(0) else begin a.popMax(u,k); writeln(k); end; 3: if a.hminsize=0 then writeln(0) else begin a.popMin(u,k); writeln(k); end; end; read(request); end; // close(input); close(output); end.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int dr[] = {0, 0, 0, -1, +1}; const int dc[] = {0, -1, +1, 0, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = ld(1e-12); const ll mod = 1000000000; typedef pair<int, int> II; #define maxn 100005 using namespace std; int id; set<II> S; set<II>::iterator it; int k, n; int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(scanf("%d", &id) > 0 && id > 0){ if(id == 1){ scanf("%d %d", &k, &n); S.insert(mp(n, k)); } else{ if(!sz(S)) printf("0\n"); else if(id == 2){ it = S.end(); it--; printf("%d\n", (*it).se); S.erase(it); } else{ it = S.begin(); printf("%d\n", (*it).se); S.erase(it); } } } }
Code mẫu của ll931110
#include <iostream> #include <set> #include <iterator> #include <utility> using namespace std; set< pair<int,int> > s; int main() { // freopen("mn.in","r",stdin); // freopen("mn.ou","w",stdout); int q; pair<int,int> u; int k1,k2; do { // cout << s.size() << endl; scanf("%d", &q); if (q == 0) break; if (q == 1) { scanf("%d%d", &k2, &k1); u = make_pair(k1,k2); s.insert(u); } else { if (s.empty()) printf("%d\n", 0); else { if (q == 2) u = *--s.end(); else u = *s.begin(); printf("%d\n", u.second); s.erase(u); }; }; } while (q != 0); };
Comments