COCI '10 Contest 5 #5 Dvoniz

Points: 12 (partial)

Time limit: 0.5s

Memory limit: 64M

Problem types

We say that a sequence of $2K$ ~2K~ elements is interesting if neither the sum of the first $K$ ~K~ elements, nor the sum of the last $K$ ~K~ elements, is greater than $S$ ~S~.

A sequence $A$ ~A~ of length $N$ ~N~ is given. For every element, output the length of the longest interesting subsequence starting with that element.

Input Specification

The first line contains integers $N$ ~N~ and $S$ ~S~ $(2 \leq N \leq 100\,000, 1 \leq S \leq 2 \times 10^9)$ .

The following $N$ ~N~ lines contain the sequence $A$ ~A~, one integer per line. The integers are positive and their sum does not exceed $2 \times 10^9$ ~2 \times 10^9~.

Output Specification

Output must consist of $N$ ~N~ lines. $i^\text{th}$ ~i^\text{th}~ line must contain one integer, the length of the longest interesting subsequence starting with the $i^\text{th}$ ~i^\text{th}~ element. If an interesting subsequence at that position doesn't exist, output $0$ ~0~ (zero).

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Comments

1

maxcruickshanks commented on May 17, 2022, 12:32 a.m.

Since the original data were weak, an additional test case was added and weighted a third of the points.

13

Plasmatic commented on March 18, 2021, 1:22 a.m.

Note that when this problem mentions "subsequence", it actually means "subarray"