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.

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

Please read the guidelines before commenting.


There are no comments at the moment.