DRASHOOT - Dragon Shooting

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
      maxn=100010;
      oo=1000000;
var n,m:longint;
    a,h,f,g:array[1..maxn shl 2] of longint;
    pos,d:array[1..maxn] of longint;

procedure add(node,l,r,x,val:longint);
var mid:longint;
begin
     if (l=x) and (r=x) then
     begin
          a[node]:=val; h[node]:=x; pos[x]:=node;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then add(node shl 1,l,mid,x,val)
          else add(node shl 1+1,mid+1,r,x,val);
          if val>a[node] then a[node]:=val;
          h[node]:=h[node shl 1];
     end;
end;

procedure rf;
var i,x:longint;
begin
     read(n);
     for i:=1 to n do
     begin
          read(x);
          add(1,1,n,i,x);
     end;
end;

function find(node,l,r,val:longint):longint;
var mid:longint;
begin
     if l=r then find:=l
     else
     begin
          mid:=(l+r) shr 1;
          val:=val+g[node];
          if h[node shl 1+1]<=val then
             find:=find(node shl 1+1,mid+1,r,val)
          else
              find:=find(node shl 1,l,mid,val);
     end;
end;

procedure update(node,l,r,x:longint);
var mid:longint;
begin
end;

procedure incr(node,l,r,x,y:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          f[node]:=f[node]+1;
          g[node]:=g[node]+1;
          h[node]:=h[node]-1;
     end
     else
     begin
          mid:=(l+r) shr 1;
          if x<=mid then incr(node shl 1,l,mid,x,min(y,mid));
          if y>mid then incr(node shl 1+1,mid+1,r,max(x,mid+1),y);
          f[node]:=max(f[node shl 1],f[node shl 1+1])+g[node];
     end;
end;

procedure update(x:longint);
begin
     while x>1 do
     begin
          x:=x shr 1;
          a[x]:=max(a[x shl 1],a[x shl 1+1]);
          h[x]:=min(h[x shl 1],h[x shl 1+1])-g[x];
     end;
end;

function find2(node,l,r,val:longint):longint;
var mid:longint;
begin
     if (l=r) then find2:=l
     else
     begin
          mid:=(l+r) shr 1;
          val:=val-g[node];
          if f[node shl 1]>=val then
             find2:=find2(node shl 1,l,mid,val)
          else find2:=find2(node shl 1+1,mid+1,r,val);
     end;
end;

procedure get(node,l,r,x,y:longint;var s:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then s:=a[node]
     else
     begin
          mid:=(l+r) shr 1;
          t:=-1; u:=-1;
          if x<=mid then get(node shl 1,l,mid,x,min(y,mid),t);
          if y>mid then get(node shl 1+1,mid+1,r,max(x,mid+1),y,u);
          s:=max(t,u);
     end;
end;

procedure pr;
var i,x,y,t,u,dem,re:longint; c:char;
begin
     readln(m); dem:=0;
     for i:=1 to m do
     begin
          read(c);
          if c='S' then
          begin
               readln(x);
               y:=find(1,1,n,x);
               a[pos[y]]:=-1; h[pos[y]]:=oo;
               if y<n then incr(1,1,n,y+1,n);
               update(pos[y]);
               dem:=dem+1;
          end
          else
          begin
               re:=-1;
               readln(x,y);
               if x>dem then
               begin
                    writeln('NONE'); continue;
               end;
               t:=find2(1,1,n,x);
               if y>=dem then u:=n
               else u:=find2(1,1,n,y+1)-1;
               get(1,1,n,t,u,re);
               if re=-1 then writeln('NONE') else writeln(re);
          end;
     end;
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download