// TODO implement optimally
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
int x, q;
int arr[500005];
int sp_tb[19][500005];
void build_sparse_table() {
for (int l = 1; l < 19; l++) {
for (int i = 1; i+(1<<l)-1 <= x; i++) {
sp_tb[l][i] = std::max(sp_tb[l-1][i],sp_tb[l-1][i+(1<<(l-1))]);
}
}
}
int max_query(int l, int r) {
int lvl = 31-__builtin_clz(r-l+1);
return std::max(sp_tb[lvl][l], sp_tb[lvl][r-(1<<lvl)+1]);
}
struct PQComp {
bool operator() (int a, int b) {
return arr[a] < arr[b];
}
};
// take the 2 maxes, let their positions be 1 and 2
// therefore we have the following cases
//
// 1: ---1##--2
// 2: --###1--2
// 3: -1-2-####
int query(int l, int r) {
if (r-l+1<=20) {
int ret = 0;
for (int i = l; i <= r; i++) {
for (int j = i+1; j <= r; j++) {
for (int k = j+(j-i); k <= r; k++) {
if (ret<arr[i]+arr[j]+arr[k]) {
ret = arr[i]+arr[j]+arr[k];
//std::cout << i << " " << j << " " << k << "\n";
}
}
}
}
return ret;
}
std::priority_queue<int, std::vector<int>, PQComp> pq;
for (int i = l; i <= r; i++) {
pq.emplace(i);
}
std::vector<int> pos;
while (!pq.empty()&&pos.size()<20) {
int k = pq.top();
pq.pop();
pos.emplace_back(k);
}
int ret = 0;
for (int i = 0; i < pos.size(); i++) {
int m1 = pos[i];
for (int j = i+1; j < pos.size(); j++) {
int m2 = pos[j];
if (m1>m2) std::swap(m1,m2);
int le, ri;
//std::cout << m1 << " " << m2 << "\n";
// 1
if (m1+1<m2) {
le = m1+1;
ri = (m1+m2)/2;
//std::cout << "1 " << le << " " << ri << "\n";
ret = std::max(ret,arr[m1]+arr[m2]+max_query(le,ri));
}
// 2
if (m1-1>=l) {
le = std::max(l,m1-(m2-m1));
ri = m1-1;
ret = std::max(ret,arr[m1]+arr[m2]+max_query(le,ri));
//std::cout << "2 " << le << " " << ri << "\n";
}
// 3
if (m2+(m2-m1)<=r) {
le = m2+(m2-m1);
ri = r;
ret = std::max(ret,arr[m1]+arr[m2]+max_query(le,ri));
//std::cout << "3 " << le << " " << ri << "\n";
}
//std::cout << "\n";
}
}
return ret;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x;
for (int i = 1; i <= x; i++) {
std::cin >> arr[i];
sp_tb[0][i] = arr[i];
}
build_sparse_table();
std::cin >> q;
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << query(l,r) << "\n";
}
}
Compilation message
jumps.cpp: In function 'int query(int, int)':
jumps.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < pos.size(); i++) {
| ~~^~~~~~~~~~~~
jumps.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int j = i+1; j < pos.size(); j++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
12624 KB |
Output is correct |
3 |
Correct |
2 ms |
12624 KB |
Output is correct |
4 |
Correct |
2 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
2 ms |
12624 KB |
Output is correct |
7 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
12624 KB |
Output is correct |
3 |
Correct |
2 ms |
12624 KB |
Output is correct |
4 |
Correct |
2 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
2 ms |
12624 KB |
Output is correct |
7 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
37328 KB |
Output is correct |
2 |
Correct |
25 ms |
37388 KB |
Output is correct |
3 |
Correct |
20 ms |
37384 KB |
Output is correct |
4 |
Correct |
23 ms |
37328 KB |
Output is correct |
5 |
Correct |
22 ms |
37328 KB |
Output is correct |
6 |
Incorrect |
18 ms |
37496 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
12624 KB |
Output is correct |
3 |
Correct |
2 ms |
12624 KB |
Output is correct |
4 |
Correct |
2 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
2 ms |
12624 KB |
Output is correct |
7 |
Incorrect |
2 ms |
12624 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |