CVJETICI - Cvjetici

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100011;
  snode=524288;
var
  f1,f2:text;
  ln,n:longint;
  l,r:array[1..MAXN] of longint;
  cover:array[1..snode] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
begin
  read(f1,n);
  for n:=1 to n do
    read(f1,l[n],r[n]);
  for n:=1 to n do
    ln:=max(ln,r[n]);
end;
procedure update(u,v,k:longint);
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (v<l) or (r<u) then exit;
    if (u<=l) and (r<=v) then
      begin
        if k=1 then cover[i]+=1
        else cover[i]:=0;
        exit;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,ln);
end;
function get(u:longint):longint;
var
  kq:longint;
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if l>r then exit;
    if (u<l) or (r<u) then exit;
    if (l=r) then
      begin
        kq:=cover[i];
        exit;
      end;
    if cover[i]>0 then
      begin
        cover[i<<1]+=cover[i];
        cover[i<<1+1]+=cover[i];
        cover[i]:=0;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,ln);
  exit(kq);
end;
procedure solve;
var
  i,x,y:longint;
begin
  for i:=1 to n do
    begin
      x:=get(l[i]);
      y:=get(r[i]);
      writeln(f2,x+y);
      update(l[i]+1,r[i]-1,1);
      update(l[i],l[i],0);
      update(r[i],r[i],0);
    end;
end;
begin
  openF;
  inp;
  solve;
  closeF;
end.

Download