Submission #1037455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037455		xnqs	Triple Jump (JOI19_jumps)	C++17	0 / 100	18 ms	5672 KiB

jumps

// TODO implement optimally

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>

int x, q;
int arr[500005];

int range_max_query(int l, int r) {
	int ret = 0;
	for (int i = l; i <= r; i++) {
		ret = std::max(ret,arr[i]);
	}
	return ret;
}

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);
	}

	int m1 = pq.top(); pq.pop();
	int m2 = pq.top(); pq.pop();
	int m3 = 0;
	int ret = arr[m1] + arr[m2];

	if (m1>m2) std::swap(m1,m2);

	// 1
	for (int i = m1+1; std::abs(m1-i) <= std::abs(m2-i); i++) {
		if (ret<arr[m1]+arr[m2]+arr[i]) {
			ret = arr[m1]+arr[m2]+arr[i];
			m3 = i;
		}
	}
	// 2
	for (int i = m1-1; std::abs(m1-i) <= std::abs(m1-m2); i--) {
		if (ret<arr[m1]+arr[m2]+arr[i]) {
			ret = arr[m1]+arr[m2]+arr[i];
			m3 = i;
		}
	}
	// 3
	for (int i = m2+(m2-m1); i <= r; i++) {
		if (ret<arr[m1]+arr[m2]+arr[i]) {
			ret = arr[m1]+arr[m2]+arr[i];
			m3 = i;
		}
	}

	//std::cout << m1 << " " << m2 << " " << m3 << "\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];
	}

	std::cin >> q;
	while (q--) {
		int l, r;
		std::cin >> l >> r;
		std::cout << query(l,r) << "\n";
	}
}

Compilation message (stderr)

jumps.cpp: In function 'int query(int, int)':
jumps.cpp:42:6: warning: variable 'm3' set but not used [-Wunused-but-set-variable]
   42 |  int m3 = 0;
      |      ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54