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$ $2 K$ 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)$ $(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^{th}$ line must contain one integer, the length of the longest interesting subsequence starting with the $i^\text{th}$ $i^{th}$ element. If an interesting subsequence at that position doesn't exist, output $0$ $0$ (zero).

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

Sample Output 3

Copy

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.

14

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

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