COCI '10 Contest 5 #5 Dvoniz

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem types

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

A sequence A of length 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 and S (2 \leq N \leq 100\,000, 1 \leq S \leq 2 \times 10^9).

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

Output Specification

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

Sample Input 1

5 10000
1
1
1
1
1

Sample Output 1

4
4
2
2
0

Sample Input 2

5 9
1
1
10
1
9

Sample Output 2

2
0
0
2
0

Sample Input 3

8 3
1
1
1
1
1
1
1
1

Sample Output 3

6
6
6
4
4
2
2
0

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.


  • 2
    SuperClash  commented on March 19, 2021, 5:53 p.m.

    Fast I/O go brrrr.


    • 0
      Ninjaclasher  commented on March 20, 2021, 1:00 a.m.

      Time limit has been reduced to 0.5s so brute force should no longer pass.


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

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