oj.uz

Submission #1107167

# Submission time Handle Problem Language Result Execution time Memory
1107167 2024-10-31T18:11:23 Z xnqs Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 38596 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()<200000) {
		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-i <= 1000; 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-i <= 1000; j++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 3 ms 12780 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 3 ms 12624 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 4 ms 12764 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 12624 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 3 ms 12780 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 3 ms 12624 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 4 ms 12764 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 12624 KB Output is correct
11 Execution timed out 4038 ms 25168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2243 ms 38596 KB Output is correct
2 Correct 1568 ms 38432 KB Output is correct
3 Correct 2186 ms 38492 KB Output is correct
4 Correct 2179 ms 38508 KB Output is correct
5 Correct 2190 ms 38496 KB Output is correct
6 Correct 2251 ms 38596 KB Output is correct
7 Incorrect 2193 ms 38596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 3 ms 12780 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 3 ms 12624 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 4 ms 12764 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 12624 KB Output is correct
11 Execution timed out 4038 ms 25168 KB Time limit exceeded
12 Halted 0 ms 0 KB -