| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
2012-02-07 05:54:07 Fish
I added if (l <= 0 || r > n) exit(1); in my code, and I received a RE(NZEC), perhaps there are something wrong with the data? |
|
|
2009-08-08 15:55:38 [Trichromatic] XilinX
Needn't use any data structures. O(1) for each update and O(m) for each query will lead to Accepted. Edit: seems there's a rejudge. Many "Accepted" solutions (mine included) don't work now. Last edit: 2009-07-03 03:53:18 |
RSS