CONANGSS - Help Conan 8 !! Hurry up !!
English | Vietnamese |
Given a sequence of n numbers (initially all is equal to 0) and m queries of two kinds:
U i j v increase all numbers from position i to position j by v (v may be negative)
Q i j query max{ap+ap+1+...+aq | i <= p <= q <= j} as in problem GSS1 and GSS3
You have to process these queries and print out the answer for each query of type Q.
The time limit for this problem is 2s.
Input
- First line: n, m (1 <= n <= 20000, 1 <= m <= 20000)
- In each line of the next m lines there is a query of one of the two forms above.
Output
For each query of type Q, print out the corresponding answer.
Example
Input:
4 2
U 1 3 2
Q 1 4
Output:
6
hide comments
Fish:
2012-02-07 05:54:07
I added
|
|
[Trichromatic] XilinX:
2009-08-08 15:55:38
Needn't use any data structures. O(1) for each update and O(m) for each query will lead to Accepted.
|
Added by: | ConanKudo |
Date: | 2008-07-15 |
Time limit: | 0.100s-6.734s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Own |