407899: GYM102920 I Stock Analysis

SY Company wants to analyze a stock. The fluctuation value, which is the difference in stock prices for two consecutive days, is the most frequently used data for the time-series analysis of the stock. It is important to utilize the largest sum of the contiguous fluctuation values. However, using the largest contiguous sum as a key indicator could be risky. As an alternative, the company utilizes the largest contiguous sum that is not greater than a predetermined value $$$U$$$ in a specified period $$$[S, E]$$$ from $$$S$$$ to $$$E$$$. The company wants to process such queries as fast as possible, where a query is defined as a predetermined value $$$U$$$ and a period $$$[S, E]$$$.

Given a collection of $$$n$$$ recent fluctuation values for some stock and $$$m$$$ queries $$$\{(S_1, E_1, U_1), \ldots , (S_m, E_m, U_m)\}$$$, write a program to find the largest sum of contiguous fluctuation values that is less than or equal to $$$U_i$$$ in the period $$$[S_i, E_i]$$$ for each query $$$(S_i, E_i, U_i)$$$.

Your program is to read from standard input. The input starts with a line containing two integers, $$$n$$$ and $$$m$$$, representing the number of fluctuation values and the number of queries respectively, where $$$1 \leq n \leq 2,000$$$ and $$$1 \leq m \leq 200,000$$$. The next line contains $$$n$$$ integers representing $$$n$$$ fluctuation values, which are numbered in chronological order from $$$1$$$ to $$$n$$$. Each of the following $$$m$$$ lines represents a query that consists of three integers, $$$S_i$$$, $$$E_i$$$, and $$$U_i$$$, where $$$[S_i, E_i]$$$ is the period from $$$S_i$$$ to $$$E_i$$$ over which the fluctuation values should be considered and $$$U_i$$$ is the value that the contiguous sum should not exceed. Note that all fluctuation values are between $$$−10^9$$$ and $$$10^9$$$, $$$1 \leq S_i \leq E_i \leq n$$$ and $$$−10^{14} \leq U_i \leq 10^{14}$$$ for $$$i = 1, \ldots , m$$$.

Your program is to write to standard output. Print exactly $$$m$$$ lines. The $$$i$$$-th line should contain the largest sum of contiguous fluctuation values that does not exceed $$$U_i$$$ and in the period $$$[S_i, E_i]$$$ for the $$$i$$$-th query. Note that every contiguous sum is the sum of one or more consecutive fluctuation values. When it is impossible to find such the sum, the program should print NONE.

5 3
1 -2 -3 5 4
1 3 -2
1 5 8
1 5 3

-2
6
2

6 4
3 8 -3 2 5 2
1 6 17
1 6 16
2 5 4
2 5 -4

17
15
4
NONE