FOCUS - Chuyên gia ruồi

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program FOCUS;
const
  input  = '';
  output = '';
  maxn = 200010;
var
  q,pos: array[1..3 * maxn] of integer;
  a,b,t: array[1..2 * maxn] of integer;
  ch: array[1..maxn] of char;
  n,num: integer;
  fi,fo: text;

procedure add(i: integer);
begin
  read(fi, q[i]);
  inc(num);
  a[num] := q[i];
  pos[num] := i;
end;

procedure init;
var
  i: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n);
  num := 0;
  for i := 1 to n do
    begin
      read(fi, ch[i]);
      if ch[i] = '?' then
        begin
          read(fi, q[3 * i]);
          add(3 * i + 1);
          add(3 * i + 2);
        end
      else add(3 * i);
      readln(fi);
    end;

  close(fi);
end;

procedure swap(var x,y: integer);
var
  tmp: integer;
begin
  tmp := x;  x := y;  y := tmp;
end;

procedure swapint(i,j: integer);
begin
  swap(a[i],a[j]);
  swap(pos[i],pos[j]);
end;

procedure quicksort;

  procedure partition(l,h: integer);
  var
    i,j,p: integer;
  begin
    if l >= h then exit;
    i := l;  j := h;  p := a[random(h - l + 1) + l];

    repeat
      while a[i] < p do inc(i);
      while a[j] > p do dec(j);

      if i <= j then
        begin
          if i < j then swapint(i,j);
          inc(i);
          dec(j);
        end;
    until i > j;

    partition(l,j);
    partition(i,h);
  end;

var
  i,c: integer;
begin
  partition(1,num);
  c := 1;
  q[pos[1]] := 1;
  b[1] := a[1];

  for i := 2 to num do
    begin
      if a[i] > a[i - 1] then inc(c);
      q[pos[i]] := c;
      b[c] := a[i];
    end;
end;

procedure update(x,k: integer);
begin
  while x <= 2 * maxn do
    begin
      t[x] := t[x] + k;
      x := x + (x and -x);
    end;
end;

function calc(x: integer): integer;
var
  r: integer;
begin
  r := 0;
  while x > 0 do
    begin
      r := r + t[x];
      x := x - (x and -x);
    end;
  calc := r;
end;

procedure solve;
var
  i,inf,sup,mid,tmp,tm,res: integer;
begin
  assign(fo, output);
    rewrite(fo);

  for i := 1 to n do
    if ch[i] = '+' then update(q[3 * i],1)
    else if ch[i] = '-' then update(q[3 * i],-1)
    else
      begin
        inf := q[3 * i + 1];
        sup := q[3 * i + 2];

        if calc(sup) - calc(inf - 1) < q[3 * i] then writeln(fo, 0) else
          begin
            tmp := calc(inf - 1);
            repeat
              mid := (inf + sup) div 2;
              tm := calc(mid);

              if tm < q[3 * i] + tmp then inf := mid + 1 else
                begin
                  res := mid;
                  sup := mid - 1;
                end;
            until inf > sup;

            writeln(fo, b[res]);
          end;
      end;

  close(fo);
end;

begin
  init;
  quicksort;
  solve;
end.

Download