#include<iostream>
#include<algorithm>
#define DIM 500005
#define f first
#define s second
using namespace std;
int n, q, i, u, nr;
int v[DIM], c[DIM], sol[DIM];
pair<int, int> p[2 * DIM];
struct str{
int x, y, ind;
};
str w[DIM];
struct str2{
int vmax, smax, cmax;
};
str2 aint[4 * DIM], curr;
int cmp(str a, str b){
return a.x > b.x;
}
void build(int nod, int st, int dr){
if(st == dr){
aint[nod].vmax = v[st];
}
else{
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod].vmax = max(aint[2 * nod].vmax, aint[2 * nod + 1].vmax);
}
}
void update(int nod, int st, int dr, int p, int u, int val){
if(p <= st && dr <= u){
aint[nod].cmax = max(aint[nod].cmax, val);
aint[nod].smax = max(aint[nod].smax, aint[nod].vmax + aint[nod].cmax);
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p, u, val);
}
if(u > mid){
update(2 * nod + 1, mid + 1, dr, p, u, val);
}
aint[nod].smax = max(aint[nod].smax, max(aint[2 * nod].smax, aint[2 * nod + 1].smax) );
}
}
str2 query(int nod, int st, int dr, int p, int u){
if(p <= st && dr <= u){
return aint[nod];
}
else{
int mid = (st + dr) / 2;
str2 a, b, curr;
a = b = {0, 0, 0};
if(p <= mid){
a = query(2 * nod, st, mid, p, u);
}
if(u > mid){
b = query(2 * nod + 1, mid + 1, dr, p, u);
}
curr.vmax = max(a.vmax, b.vmax);
curr.cmax = aint[nod].cmax;
curr.smax = max(curr.vmax + curr.cmax, max(a.smax, b.smax) );
return curr;
}
}
int main(){
cin>> n;
for(i = 1; i <= n; i++){
cin>> v[i];
}
for(i = n; i >= 1; i--){
while(u > 0 && v[ c[u] ] < v[i]){
p[++nr] = make_pair(i, c[u]);
u--;
}
if(u > 0){
p[++nr] = make_pair(i, c[u]);
}
c[++u] = i;
}
sort(p + 1, p + nr + 1);
build(1, 1, n);
cin>> q;
for(i = 1; i <= q; i++){
cin>> w[i].x >> w[i].y;
w[i].ind = i;
}
sort(w + 1, w + q + 1, cmp);
u = nr;
for(i = 1; i <= q; i++){
while(u > 0 && p[u].f >= w[i].x){
if(p[u].s + p[u].s - p[u].f <= n){
update(1, 1, n, p[u].s + p[u].s - p[u].f, n, v[ p[u].f ] + v[ p[u].s ]);
}
u--;
}
curr = query(1, 1, n, w[i].x, w[i].y);
sol[ w[i].ind ] = curr.smax;
}
for(i = 1; i <= q; i++){
cout<< sol[i] <<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
816 ms |
18296 KB |
Output is correct |
12 |
Correct |
810 ms |
18168 KB |
Output is correct |
13 |
Correct |
825 ms |
18168 KB |
Output is correct |
14 |
Correct |
815 ms |
18172 KB |
Output is correct |
15 |
Correct |
815 ms |
18168 KB |
Output is correct |
16 |
Correct |
827 ms |
17532 KB |
Output is correct |
17 |
Correct |
816 ms |
17528 KB |
Output is correct |
18 |
Correct |
811 ms |
17528 KB |
Output is correct |
19 |
Correct |
796 ms |
18040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
268 ms |
12196 KB |
Output is correct |
2 |
Correct |
210 ms |
11368 KB |
Output is correct |
3 |
Correct |
206 ms |
10744 KB |
Output is correct |
4 |
Correct |
266 ms |
12168 KB |
Output is correct |
5 |
Correct |
264 ms |
12152 KB |
Output is correct |
6 |
Correct |
215 ms |
11512 KB |
Output is correct |
7 |
Correct |
207 ms |
11384 KB |
Output is correct |
8 |
Correct |
209 ms |
11384 KB |
Output is correct |
9 |
Correct |
232 ms |
11896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
816 ms |
18296 KB |
Output is correct |
12 |
Correct |
810 ms |
18168 KB |
Output is correct |
13 |
Correct |
825 ms |
18168 KB |
Output is correct |
14 |
Correct |
815 ms |
18172 KB |
Output is correct |
15 |
Correct |
815 ms |
18168 KB |
Output is correct |
16 |
Correct |
827 ms |
17532 KB |
Output is correct |
17 |
Correct |
816 ms |
17528 KB |
Output is correct |
18 |
Correct |
811 ms |
17528 KB |
Output is correct |
19 |
Correct |
796 ms |
18040 KB |
Output is correct |
20 |
Correct |
268 ms |
12196 KB |
Output is correct |
21 |
Correct |
210 ms |
11368 KB |
Output is correct |
22 |
Correct |
206 ms |
10744 KB |
Output is correct |
23 |
Correct |
266 ms |
12168 KB |
Output is correct |
24 |
Correct |
264 ms |
12152 KB |
Output is correct |
25 |
Correct |
215 ms |
11512 KB |
Output is correct |
26 |
Correct |
207 ms |
11384 KB |
Output is correct |
27 |
Correct |
209 ms |
11384 KB |
Output is correct |
28 |
Correct |
232 ms |
11896 KB |
Output is correct |
29 |
Correct |
1891 ms |
46236 KB |
Output is correct |
30 |
Correct |
1722 ms |
44272 KB |
Output is correct |
31 |
Correct |
1718 ms |
42400 KB |
Output is correct |
32 |
Correct |
1857 ms |
46200 KB |
Output is correct |
33 |
Correct |
1865 ms |
46200 KB |
Output is correct |
34 |
Correct |
1736 ms |
43896 KB |
Output is correct |
35 |
Correct |
1725 ms |
43640 KB |
Output is correct |
36 |
Correct |
1730 ms |
43640 KB |
Output is correct |
37 |
Correct |
1781 ms |
45048 KB |
Output is correct |
38 |
Correct |
1702 ms |
46200 KB |
Output is correct |
39 |
Correct |
1681 ms |
46332 KB |
Output is correct |
40 |
Correct |
1597 ms |
42904 KB |
Output is correct |
41 |
Correct |
1570 ms |
42616 KB |
Output is correct |
42 |
Correct |
1558 ms |
42588 KB |
Output is correct |
43 |
Correct |
1629 ms |
44332 KB |
Output is correct |
44 |
Correct |
1697 ms |
46444 KB |
Output is correct |
45 |
Correct |
1715 ms |
46396 KB |
Output is correct |
46 |
Correct |
1608 ms |
43184 KB |
Output is correct |
47 |
Correct |
1579 ms |
42768 KB |
Output is correct |
48 |
Correct |
1577 ms |
42872 KB |
Output is correct |
49 |
Correct |
1656 ms |
44792 KB |
Output is correct |
50 |
Correct |
1762 ms |
46308 KB |
Output is correct |
51 |
Correct |
1750 ms |
46440 KB |
Output is correct |
52 |
Correct |
1632 ms |
44152 KB |
Output is correct |
53 |
Correct |
1616 ms |
43524 KB |
Output is correct |
54 |
Correct |
1616 ms |
43512 KB |
Output is correct |
55 |
Correct |
1649 ms |
45304 KB |
Output is correct |