За один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K

unit OsTree;
{$mode objfpc}
interface
 
uses
  SysUtils;
 
type
  TOsTree = class
  private
  type
    PNode = ^TNode;
    TNode = record
      Left, Right: PNode;
      Value, Size: Int32;
      Prio: UInt32;
      Sum: Int64;
    end;
  var
    FRoot: PNode;
    class function  NextRandom: UInt32; static;
    class function  NewNode(aValue: Int32): PNode; static;
    class procedure ClearNode(aNode: PNode); static;
    class procedure Update(aNode: PNode); static;
    class function  GetNodeSize(aNode: PNode): SizeInt; static;
    class function  NodeByIndex(aRoot: PNode; aIndex: Int32): PNode; static;
    class procedure SplitNode(aKeyValue: Int32; aRoot: PNode; out L, R: PNode); static;
    class procedure SplitNodeI(aIdx: Int32; aRoot: PNode; out L, R: PNode); static;
    class function  MergeNode(L, R: PNode): PNode; static;
    class procedure AddNode(var aRoot: PNode; aNode: PNode); static;
    class function  RemoveNode(aKeyValue: Int32; var aRoot: PNode): Boolean; static;
    function  GetCount: Int32;
    procedure CheckIndexRange(aIndex: SizeInt);
    function  GetItem(aIndex: Int32): Int32;
  public
    destructor Destroy; override;
    function  IsEmpty: Boolean;
    procedure Clear;
    procedure Add(aValue: Int32);
    function  Remove(aValue: Int32): Boolean;
  { возвращает сумму элементов на отрезке [0, aIndex] }
    function  HeadSum(aIndex: Int32): Int64;
  { возвращает сумму элементов на отрезке [aIndex, Count-1] }
    function  TailSum(aIndex: Int32): Int64;
    property  Count: Int32 read GetCount;
    property  Items[aIndex: Int32]: Int32 read GetItem; default;
  end;
 
implementation
 
class function TOsTree.NextRandom: UInt32;
begin
  Result := UInt32(Random(Int64(High(UInt32)) + 1));
end;
 
class function TOsTree.NewNode(aValue: Int32): PNode;
begin
  New(Result);
  with Result^ do begin
    Left := nil;
    Right := nil;
    Value := aValue;
    Size := 1;
    Prio := NextRandom;
    Sum := aValue;
  end;
end;
 
class procedure TOsTree.ClearNode(aNode: PNode);
begin
  if aNode <> nil then begin
    ClearNode(aNode^.Left);
    ClearNode(aNode^.Right);
    Dispose(aNode);
  end;
end;
 
class procedure TOsTree.Update(aNode: PNode);
begin
  with aNode^ do begin
    Size := 1;
    Sum := aNode^.Value;
    if Left <> nil then begin
      Size += Left^.Size;
      Sum += Left^.Sum;
    end;
    if Right <> nil then begin
      Size += Right^.Size;
      Sum += Right^.Sum;
    end;
  end;
end;
 
class function TOsTree.GetNodeSize(aNode: PNode): SizeInt;
begin
  if aNode = nil then exit(0);
  Result := aNode^.Size;
end;
 
class function TOsTree.NodeByIndex(aRoot: PNode; aIndex: Int32): PNode;
var
  LSize: Int32;
begin
  while aRoot <> nil do begin
    LSize := GetNodeSize(aRoot^.Left);
    if LSize < aIndex then begin
      aRoot := aRoot^.Right;
      aIndex -= LSize + 1;
    end else
      if LSize > aIndex then
        aRoot := aRoot^.Left
      else
        exit(aRoot);
  end;
  Result := aRoot;
end;
 
class procedure TOsTree.SplitNode(aKeyValue: Int32; aRoot: PNode; out L, R: PNode);
begin
  if aRoot <> nil then begin
    if aRoot^.Value < aKeyValue then begin
      L := aRoot;
      SplitNode(aKeyValue, L^.Right, L^.Right, R);
    end else begin
      R := aRoot;
      SplitNode(aKeyValue, R^.Left, L, R^.Left);
    end;
    Update(aRoot);
    exit;
  end else begin
    L := nil;
    R := nil;
  end;
end;
 
class procedure TOsTree.SplitNodeI(aIdx: Int32; aRoot: PNode; out L, R: PNode);
var
  LIdx: Int32;
begin
  if aRoot <> nil then begin
    LIdx := GetNodeSize(aRoot^.Left);
    if LIdx < aIdx then begin
      L := aRoot;
      SplitNodeI(aIdx - LIdx - 1, L^.Right, L^.Right, R);
    end else begin
      R := aRoot;
      SplitNodeI(aIdx, R^.Left, L, R^.Left);
    end;
    Update(aRoot);
  end else begin
    L := nil;
    R := nil;
  end;
end;
 
class function TOsTree.MergeNode(L, R: PNode): PNode;
begin
  if L = nil then
    Result := R
  else
    if R = nil then
      Result := L
    else begin
      if L^.Prio > R^.Prio then begin
        L^.Right := MergeNode(L^.Right, R);
        Result := L;
      end else begin
        R^.Left := MergeNode(L, R^.Left);
        Result := R;
      end;
      Update(Result);
    end;
end;
 
class procedure TOsTree.AddNode(var aRoot: PNode; aNode: PNode);
begin
  if aRoot <> nil then begin
    if aRoot^.Prio < aNode^.Prio then begin
      SplitNode(aNode^.Value, aRoot, aNode^.Left, aNode^.Right);
      aRoot := aNode;
    end else
      if aNode^.Value < aRoot^.Value then
        AddNode(aRoot^.Left, aNode)
      else
        AddNode(aRoot^.Right, aNode);
    Update(aRoot);
  end else
    aRoot := aNode;
end;
 
class function TOsTree.RemoveNode(aKeyValue: Int32; var aRoot: PNode): Boolean;
var
  Node: PNode;
begin
  if aRoot = nil then exit(False);
  if aKeyValue < aRoot^.Value then begin
    Result := RemoveNode(aKeyValue, aRoot^.Left);
    if Result then Update(aRoot);
  end else
    if aRoot^.Value < aKeyValue then begin
      Result := RemoveNode(aKeyValue, aRoot^.Right);
      if Result then Update(aRoot);
    end else begin
      Node := aRoot;
      aRoot := MergeNode(aRoot^.Left, aRoot^.Right);
      Dispose(Node);
      Result := True;
    end;
end;
 
function TOsTree.GetCount: Int32;
begin
  Result := GetNodeSize(FRoot);
end;
 
procedure TOsTree.CheckIndexRange(aIndex: SizeInt);
begin
  if UInt32(aIndex) >= UInt32(Count) then
    raise EArgumentOutOfRangeException.CreateFmt('Index out of bounds(%d)', [aIndex]);
end;
 
function TOsTree.GetItem(aIndex: Int32): Int32;
begin
  CheckIndexRange(aIndex);
  Result := NodeByIndex(FRoot, aIndex)^.Value;
end;
 
destructor TOsTree.Destroy;
begin
  Clear;
  inherited;
end;
 
function TOsTree.IsEmpty: Boolean;
begin
  Result := FRoot = nil;
end;
 
procedure TOsTree.Clear;
begin
  ClearNode(FRoot);
  FRoot := nil;
end;
 
procedure TOsTree.Add(aValue: Int32);
var
  p: PNode;
begin
  p := NewNode(aValue);
  if FRoot <> nil then
    AddNode(FRoot, p)
  else
    FRoot := p;
end;
 
function TOsTree.Remove(aValue: Int32): Boolean;
begin
  if FRoot = nil then exit(False);
  Result := RemoveNode(aValue, FRoot);
end;
 
function TOsTree.HeadSum(aIndex: Int32): Int64;
var
  pL, pR: PNode;
begin
  CheckIndexRange(aIndex);
  if aIndex < Pred(FRoot^.Size) then begin
    SplitNodeI(aIndex + 1, FRoot, pL, pR);
    if pL <> nil then
      Result := pL^.Sum
    else
      Result := 0;
    FRoot := MergeNode(pL, pR);
  end else
    Result := FRoot^.Sum;
end;
 
function TOsTree.TailSum(aIndex: Int32): Int64;
var
  pL, pR: PNode;
begin
  CheckIndexRange(aIndex);
  if aIndex > 0 then begin
    SplitNodeI(aIndex, FRoot, pL, pR);
    if pR <> nil then
      Result := pR^.Sum
    else
      Result := 0;
    FRoot := MergeNode(pL, pR);
  end else
    Result := FRoot^.Sum;
end;
 
end.

program test;
{$mode objfpc}
uses
  SysUtils, OsTree;
 
var
  N: Int32 = 0;
  K: Int32 = 0;
  A: array of Int32 = nil;
 
procedure ReadInput;
var
  I: Int32;
begin
  Read(N);
  ReadLn(K);
  SetLength(A, N);
  for I := 0 to High(A) do
    Read(A[I]);
end;
 
function GetMoveCount(aTree: TOsTree): Int64;
var
  Size, Mid: Int32;
begin
  if aTree.IsEmpty then exit(0);
  Size := aTree.Count;
  Mid := Size div 2 - Ord(not Odd(Size));
  if Size > 1 then
    if Odd(Size) then
      Result := aTree[Mid] + aTree.TailSum(Mid + 1) - aTree.HeadSum(Mid)
    else
      Result := aTree.TailSum(Mid + 1) - aTree.HeadSum(Mid)
  else
    Result := aTree[Mid];
end;
 
var
  MaxLen: Int32 = 1;
  LeftIdx: Int32 = 0;
  RightIdx: Int32 = 0;
 
procedure TestMaxLen(L, R: Int32);
begin
  if Succ(R - L) <= MaxLen then exit;
  MaxLen := Succ(R - L);
  LeftIdx := L;
  RightIdx := R;
end;
 
procedure SearchFor;
var
  Tree: TOsTree;
  MoveCount: Int64;
  L, R: Int32;
begin
  L := 0;
  R := -1;
  Tree := TOsTree.Create;
  try
    while R < N - 1 do begin
      Inc(R);
      Tree.Add(A[R]);
      if GetMoveCount(Tree) <= K then
        TestMaxLen(L, R)
      else begin
        repeat
          Tree.Remove(A[L]);
          Inc(L);
          MoveCount := GetMoveCount(Tree);
        until (MoveCount <= K) or (L = R) or (N - L < MaxLen);
        if MoveCount <= K then
          TestMaxLen(L, R);
      end;
    end;
  finally
    Tree.Free;
  end;
end;
 
begin
  ReadInput;
  SearchFor;
  WriteLn('Length = ', MaxLen, ', starts at ', LeftIdx, ', ends at ', RightIdx);
end.

  Result := 0;

unit MvCtr;
{$mode delphi}
interface
 
uses
  SysUtils, LgUtils, LgPriorityQueue;
 
type
  THandle = LgPriorityQueue.THandle;
  TIndexedInt = record
    Value, Index: Int32;
    constructor Make(v, i: Int32);
  end;
 
  TIdxIntCmp = record
    class function Less(const L, R: TIndexedInt): Boolean; static;
  end;
 
  TIdxIntCmpInv = record
    class function Less(const L, R: TIndexedInt): Boolean; static;
  end;
 
  TQueue = class
  private
    FQueue: IGPriorityQueue<TIndexedInt>;
    FMap: array of THandle;
    FSum: Int64;
    function GetCount: Int32;
  public
    constructor Create(aSize: Int32; aQueue: IGPriorityQueue<TIndexedInt>);
    destructor Destroy; override;
    procedure Push(const aEl: TIndexedInt);
    function  Remove(aIndex: Int32): Boolean;
    function  Contains(aIndex: Int32): Boolean;
    function  TryPeek(out aValue: Int32): Boolean;
    function  Pop: TIndexedInt;
    property  Count: Int32 read GetCount;
    property  Sum: Int64 read FSum;
  end;
 
  TMvCounter = class
  private
    FLoHalf,
    FHiHalf: TQueue;
    FMedian,
    FSize,
    FCount: Int32;
    procedure DoAdd(aValue, aIndex: Int32);
    procedure Changed;
  public
    constructor Create(aSize: Int32);
    destructor Destroy; override;
    procedure Add(aValue, aIndex: Int32);
    function  Remove(aIndex: Int32): Boolean;
    function  GetMoveCount: Int64;
  end;
 
implementation
{$coperators on}
constructor TIndexedInt.Make(v, i: Int32);
begin
  Value := v;
  Index := i;
end;
 
class function TIdxIntCmp.Less(const L, R: TIndexedInt): Boolean;
begin
  Result := L.Value < R.Value;
end;
 
class function TIdxIntCmpInv.Less(const L, R: TIndexedInt): Boolean;
begin
  Result := R.Value < L.Value;
end;
 
function TQueue.GetCount: Int32;
begin
  Result := FQueue.Count;
end;
 
constructor TQueue.Create(aSize: Int32; aQueue: IGPriorityQueue<TIndexedInt>);
begin
  SetLength(FMap, aSize);
  FQueue := aQueue;
end;
 
destructor TQueue.Destroy;
begin
  FQueue._GetRef.Free;
  inherited;
end;
 
procedure TQueue.Push(const aEl: TIndexedInt);
begin
  FMap[aEl.Index] := FQueue.Insert(aEl);
  FSum += aEl.Value;
end;
 
function TQueue.Remove(aIndex: Int32): Boolean;
begin
  if FMap[aIndex] = 0 then exit(False);
  FSum -= FQueue.Remove(FMap[aIndex]).Value;
  FMap[aIndex] := 0;
  Result := True;
end;
 
function TQueue.Contains(aIndex: Int32): Boolean;
begin
  Result := FMap[aIndex] <> 0;
end;
 
function TQueue.TryPeek(out aValue: Int32): Boolean;
var
  v: TIndexedInt;
begin
  Result := FQueue.TryPeek(v);
  if Result then aValue := v.Value;
end;
 
function TQueue.Pop: TIndexedInt;
begin
  Result := FQueue.Dequeue;
  FSum -= Result.Value;
  FMap[Result.Index] := 0;
end;
 
procedure TMvCounter.DoAdd(aValue, aIndex: Int32);
begin
  Inc(FCount);
  if FCount = 1 then
    FLoHalf.Push(TIndexedInt.Make(aValue, aIndex))
  else begin
    if aValue < FMedian then
      FLoHalf.Push(TIndexedInt.Make(aValue, aIndex))
    else
      FHiHalf.Push(TIndexedInt.Make(aValue, aIndex));
    Changed;
  end;
end;
 
procedure TMvCounter.Changed;
begin
  if Odd(FCount) then
    if FLoHalf.Count < FHiHalf.Count then
      FLoHalf.Push(FHiHalf.Pop) else
  else
    if FLoHalf.Count < FHiHalf.Count then
      FLoHalf.Push(FHiHalf.Pop)
    else
      if FLoHalf.Count > FHiHalf.Count then
        FHiHalf.Push(FLoHalf.Pop);
  FLoHalf.TryPeek(FMedian);
end;
 
constructor TMvCounter.Create(aSize: Int32);
begin
  if aSize > 0 then FSize := aSize;
  FLoHalf := TQueue.Create(FSize, TGBasePairingHeap<TIndexedInt, TIdxIntCmp>.Create);
  FHiHalf := TQueue.Create(FSize, TGBasePairingHeap<TIndexedInt, TIdxIntCmpInv>.Create);
end;
 
destructor TMvCounter.Destroy;
begin
  FLoHalf.Free;
  FHiHalf.Free;
  inherited;
end;
 
procedure TMvCounter.Add(aValue, aIndex: Int32);
begin
  if UInt32(aIndex) >= UInt32(FSize) then
    raise Exception.CreateFmt('Index out of bounds(%d)', [aIndex]);
  if FLoHalf.Contains(aIndex) or FHiHalf.Contains(aIndex) then
    raise Exception.Create('Index already added');
  DoAdd(aValue, aIndex);
end;
 
function TMvCounter.Remove(aIndex: Int32): Boolean;
begin
  Result := FLoHalf.Remove(aIndex) or FHiHalf.Remove(aIndex);
  if Result then begin
    Dec(FCount);
    Changed;
  end;
end;
 
function TMvCounter.GetMoveCount: Int64;
begin
  if FCount < 2 then exit(0);
  if Odd(FCount) then
    Result := FMedian + FHiHalf.Sum - FLoHalf.Sum
  else
    Result := FHiHalf.Sum - FLoHalf.Sum;
end;
 
end.

{$mode objfpc}
uses
  SysUtils, MvCtr;
 
var
  N: Int32 = 0;
  K: Int32 = 0;
  MaxLen: Int32 = 1;
  Left: Int32 = 0;
  Right: Int32 = 0;
  A: array of Int32 = nil;
 
procedure TestMaxLen(L, R: Int32);
begin
  if Succ(R - L) <= MaxLen then exit;
  MaxLen := Succ(R - L);
  Left := L;
  Right := R;
end;
 
procedure Solve;
var
  MvCount: Int64;
  L, R: Int32;
begin
  L := 0;
  R := -1;
  with TMvCounter.Create(N) do
    try
      while R < N - 1 do begin
        Inc(R);
        Add(A[R], R);
        MvCount := GetMoveCount;
        while (MvCount > K) and (L < R) and (N - L > MaxLen) do begin
          Remove(L);
          Inc(L);
          MvCount := GetMoveCount;
        end;
        if MvCount <= K then TestMaxLen(L, R)
      end;
    finally
      Free;
    end;
end;
 
var
  I: Int32;
begin
  ReadLn(N, K);
  SetLength(A, N);
  for I := 0 to High(A) do Read(A[I]);
  Solve;
  WriteLn('Length = ', MaxLen, ', starts at ', Left, ', ends at ', Right);
end.