이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |