# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1107154 |
2024-10-31T17:58:43 Z |
xnqs |
Triple Jump (JOI19_jumps) |
C++17 |
|
4000 ms |
37440 KB |
// 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) {
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()<50) {
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:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < pos.size(); i++) {
| ~~^~~~~~~~~~~~
jumps.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int j = i+1; j < pos.size(); j++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
3 ms |
12624 KB |
Output is correct |
7 |
Correct |
2 ms |
12624 KB |
Output is correct |
8 |
Correct |
3 ms |
12624 KB |
Output is correct |
9 |
Correct |
3 ms |
12624 KB |
Output is correct |
10 |
Correct |
3 ms |
12780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
3 ms |
12624 KB |
Output is correct |
7 |
Correct |
2 ms |
12624 KB |
Output is correct |
8 |
Correct |
3 ms |
12624 KB |
Output is correct |
9 |
Correct |
3 ms |
12624 KB |
Output is correct |
10 |
Correct |
3 ms |
12780 KB |
Output is correct |
11 |
Execution timed out |
4059 ms |
26028 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
37440 KB |
Output is correct |
2 |
Correct |
24 ms |
37328 KB |
Output is correct |
3 |
Correct |
20 ms |
37328 KB |
Output is correct |
4 |
Correct |
32 ms |
37428 KB |
Output is correct |
5 |
Correct |
24 ms |
37328 KB |
Output is correct |
6 |
Incorrect |
20 ms |
37328 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
3 ms |
12624 KB |
Output is correct |
5 |
Correct |
2 ms |
12624 KB |
Output is correct |
6 |
Correct |
3 ms |
12624 KB |
Output is correct |
7 |
Correct |
2 ms |
12624 KB |
Output is correct |
8 |
Correct |
3 ms |
12624 KB |
Output is correct |
9 |
Correct |
3 ms |
12624 KB |
Output is correct |
10 |
Correct |
3 ms |
12780 KB |
Output is correct |
11 |
Execution timed out |
4059 ms |
26028 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |