VPARTSUM - Tổng bộ phận

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  FINP='';
  FOUT='';
  MAXN=1000111;
var
  c,ln,a,sum:array[0..MAXN] of int64;
  best,sl,n,p,k:int64;
  test:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n,k,p);
  fillchar(a,sizeof(a),0);
  fillchar(sum,sizeof(sum),0);
  fillchar(ln,sizeof(ln),0);
  fillchar(c,sizeof(c),0);
  for i:=1 to n do read(f1,a[i]);
  for i:=1 to n do sum[i]:=(sum[i-1]+a[i]) mod p;
  sum[n+1]:=0;
end;
procedure swap(var a,b:int64); inline;
var
  temp:int64;
begin
  temp:=a; a:=b; b:=temp;
end;
var
  mid:int64;
procedure sort(l,r:int64); inline;
var
  i,j:int64;
begin
  mid:=c[l+random(r-l+1)]; i:=l; j:=r;
  repeat
    while c[i]<mid do inc(i);
    while c[j]>mid do dec(j);
    if i<=j then
      begin
        swap(c[i],c[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure init;
var
  i:longint;
begin
  for i:=1 to n+1 do c[i]:=sum[i];
  sort(1,n+1);
  sl:=1;
  for i:=2 to n+1 do
    if c[i]>c[sl] then
      begin
        inc(sl);
        c[sl]:=c[i];
      end;
end;
function get(u:int64):int64; inline;
var
  kq,v:int64;
begin
  if u<=0 then exit(0);
  kq:=ln[u];
  v:=u-u and (-u);
  if v>0 then kq:=max(kq,get(v));
  exit(kq);
end;
procedure update(u,k:int64); inline;
var
  v:int64;
begin
  ln[u]:=max(ln[u],k);
  v:=u+u and (-u);
  if v<=sl then update(v,k);
end;
function find(x:int64):int64; inline;
var
  l,r,kq:int64;
begin
  l:=1; r:=sl; kq:=0;
  repeat
    mid:=(l+r)>>1;
    if c[mid]<=x then
      begin kq:=mid; l:=mid+1; end
    else r:=mid-1;
  until l>r;
  exit(kq);
end;
procedure solve;
var
  u,temp:int64;
  i:longint;
begin
  best:=maxlongint;
  for i:=1 to n do
    begin
      if sum[i]>=k then
        begin
          u:=find(sum[i]-k);
          best:=min(best,sum[i]-get(u));
        end;
      u:=find(sum[i]+p-k);
      temp:=get(u);
      if temp>sum[i] then best:=min(best,sum[i]-temp+p);
      u:=find(sum[i]);
      update(u,sum[i]);
    end;
end;
procedure ans;
begin
  writeln(f2,best);
end;
begin
  openF;
//  readln(f1,test);
  test:=1;
  for test:=1 to test do
    begin
      inp;
      init;
      solve;
      ans;
    end;
  closeF;
end.

Download