|
|
SPOJ Problem Set (classical)
1557. Can you answer these queries II
Problem code: GSS2
|
Being a completist and a simplist, kid Yang Zhe cannot solve but
get Wrong Answer from most of the OI problems. And he refuse to
write two program of same kind at all. So he always failes in
contests.
When having a contest, Yang Zhe looks at the score of every
problems first. For the problems of the same score, Yang Zhe will
do only one of them. If he's lucky enough, he can get all the scores
wanted.
Amber is going to hold a contest in SPOJ. She has made a list of
N candidate problems, which fit Yang Zhe very well. So Yang
Zhe can solve any problem he want. Amber lined up the problems,
began to select. She will select a subsequence of the list as the
final problems. Being A girl of great compassion, she'd like to
select such a subsequence (can be empty) that Yang Zhe will get the
maximal score over all the possible subsequences.
Amber found the subsequence easily after a few minutes. To make
things harder, Amber decided that, Yang Zhe can take this contest
only if Yang Zhe can answer her Q questions. The question is:
if the final problems are limited to be a subsequence
of list[X..Y] (1 <= X <= Y <= N),
what's the maximal possible score Yang Zhe can get?
As we know, Yang Zhe is a bit idiot (so why did he solve the
problem with a negative score?), he got Wrong Answer again... Tell
him the correct answer!
Input
- Line 1: integer N (1 <= N <= 100000);
- Line 2: N integers denoting the score of each problem,
each of them is a integer in range [-100000, 100000];
- Line 3: integer Q (1 <= Q <= 100000);
- Line 3+i (1 <= i <= Q): two
integers X and
Y denoting the ith question.
Output
- Line i: a single integer, the answer to the ith
question.
Example
Input:
9
4 -2 -2 3 -1 -4 2 2 -6
3
1 2
1 5
4 9
Output:
4
5
3
Warning: large input/output data,be careful with certain languages
| Added by: | [Trichromatic] XilinX |
| Date: | 2007-05-16 |
| Time limit: | 1s-5s |
| Source limit: | 50000B |
| Languages: | All except: C99 strict CLOJ ERL F# JS PERL 6 TECS |
| Resource: | Description, standard program and test data by Yang Zhe |
|
|
|
|
RSS