Comeback
Time limit1sMemory limit512 MB
For each left rotation of the array, count all contiguous subsequences whose sum is at most X and report both their count and the total of their sums.
- Level
Hard8 of 10
- Topics
- Two pointers, Sliding window, Prefix sum, Array
- Solved
- No attempts yet
Problem
After visiting the Public Garden, Antonio returns home, where he finds a string of n non-negative integers and a number X. Feeling bored, he decides to invent a game with this array in n steps. At each step, Antonio performs two actions:
- He determines all the subsequences of the array whose sums are smaller or equal to X and keeps in mind the sum of the sums of such subsequences and their number.
- He circularly permutes the array to the left by one position.
Determine the values kept in mind by Antonio at each step.
Input
The first line of the input contains the numbers n and X.
On the second line there are n space-separated elements corresponding to the array.
Output
The output has n lines:
The ith line contains two integers separated by a space, the sum of the sums of valid subsequences at step i and their number.
Constraints
- n ≤ 100,000, X ≤ 1,000,000,000
- The elements of the array are between 0 and 10^6.
- A subsequence of the given array consists of elements found on consecutive positions.
Hint
- Stage 1. The sum of the sums of valid subsequences: 1 + 2 + 3 + (1 + 2) + (2 + 3) = 14. There are 5 valid subsequences. The array becomes 2, 3, 1.
- Stage 2. The sum of the sums of valid subsequences: 2 + 3 + 1 + (2 + 3) + (3 + 1) = 15. There are 5 valid subsequences. The array becomes 3, 1, 2.
- Stage 3. The sum of the sums of valid subsequences: 3 + 1 + 2 + (3 + 1) + (1 + 2) = 13. There are 5 valid subsequences. The array becomes 1, 2, 3.