Hướng dẫn giải của Double Queue
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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); };
Bình luận