Advertisement
Guest User

Untitled

a guest
Apr 1st, 2017
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var s:array[0..1000000] of int64;
  2.     a:array[1..1000000] of longint;
  3.     n,m,i:longint;
  4.     l,r,ans:int64;
  5. procedure qs(m,t:longint);
  6.     var i,j,w,x,ind:longint;
  7. begin
  8.     i:=m;
  9.     j:=t;
  10.     randomize;
  11.     ind:=m+random(t-m+1);
  12.     x:=s[ind];
  13.     repeat 
  14.         while s[i]<x do inc(i);
  15.         while s[j]>x do dec(j);
  16.         if i<=j then begin
  17.                          w:=s[i];
  18.                          s[i]:=s[j];
  19.                          s[j]:=w;
  20.                          inc(i);
  21.                          dec(j);
  22.                      end;
  23.     until i>j;
  24.     if m<j then qs(m,j);
  25.     if i<t then qs(i,t);
  26. end;
  27. begin
  28. assign(input,'input.txt');
  29. assign(output,'output.txt');
  30. reset(input);
  31. rewrite(output);
  32. readln(n,m);
  33.     ans:=0;
  34.     for i:=1 to n do
  35.         read(a[i]);
  36.     s[0]:=1;
  37.     for i:=1 to n do
  38.         s[i]:=s[i-1]+a[i];
  39.     qs(0,n);
  40.     l:=0;
  41.     r:=0;
  42.     for i:=0 to n do begin
  43.         while s[l]-s[i]>m do inc(l);
  44.         while (r<=n) and (s[r]-s[i]<=m) do  inc(r);
  45.         ans:=ans+(l+(n+1-r));
  46.     end;
  47.  writeln(ans);
  48. close(input);
  49. close(output);
  50. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement