Cod sursa(job #410237)

Utilizator hungntnktpHungntnktp hungntnktp Data 4 martie 2010 10:49:42
Problema Secventa 5 Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.1 kb
{DINH QUANG DAT TIN 07-10}
{SEQ5}
{$inline on}
{$mode objfpc}
CONST
 TFI='secv5.in';
 TFO='secv5.out';
 MAX=1 shl 20+1;
 e=301011;
TYPE
 arr1int=array[0..MAX] of longint;
VAR
 fi,fo:text;
 m,l,r,n:longint;
 next,f,a:arr1int;
 res:int64;
 head,last:array[0..e] of longint;

PROCEDURE       input;inline;
var
 i:longint;
begin
 assign(fi,tfi);reset(fi);
  read(fi,n,l,r);
  for i:= 1 to n do read(fi,a[i]);
 close(fi);
end;

PROCEDURE       init;
begin
end;

PROCEDURE       init_hash;inline;
begin
 fillchar(head,sizeof(head),0);
 fillchar(next,sizeof(next),0);
 m:=0;
end;

FUNCTION        push(x:longint):longint;inline;
var
 u,v:longint;
begin
 u:= x mod e;
 inc(m);
 f[m]:=x;
 if head[u]=0 then
  begin
   head[u]:=m;
   last[u]:=m;
   exit(1);
  end
 else
  begin
   v:=head[u];
   next[last[u]]:=m;
   last[u]:=m;
   while v<>m do
    begin
     if (f[v]=x) then exit(0);
     v:=next[v];
    end;
   exit(1);
  end;
end;

FUNCTION        del(x:longint):longint;inline;
var
 i,u,v,sl:longint;
begin
 u:= x mod e;
 v:=head[u];
 sl:=0;
 i:=0;
 while v<>0 do
  begin
   if f[v]=x then
    begin
     if sl=1 then exit(0);
     if head[u]=v then head[u]:=next[v];
     if last[u]=v then last[u]:=i;
     sl:=1;
    end;
   i:=v;
   v:=next[v];
  end;
 exit(1);
end;

FUNCTION        count(x:longint):int64;inline;
var
 sl,last,i,j:longint;
begin
 init_hash;
 count:=0;
 sl:=0;
 last:=0;
 if x=0 then exit(0);
 for i:= 1 to n do
  begin
   if (i>1) then sl:=sl-del(a[i-1]);
   if sl<=x then
    begin
     j:=last+1;
     while j<=n do
      begin
       sl:=sl+push(a[j]);
       if sl>x then
        begin
         last:=j;
         break;
        end;
       inc(j);
      end;
     if j=n+1 then last:=n+1;
    end;
   count:=count+last-i;
  end;
end;

PROCEDURE       process;inline;
var
 x,y:int64;
begin
 x:=count(l-1);
 y:=count(r);
 res:=y-x;
end;

PROCEDURE       output;inline;
begin
 assign(fo,tfo);rewrite(fo);
  writeln(fo,res);
 close(fo);
end;

BEGIN
 input;
 init;
 process;
 output;
END.