Submission #360199

#	Time	Username	Problem	Language	Result	Execution time	Memory
360199		dimashii	Triple Jump (JOI19_jumps)	C++17	0 / 100	126 ms	25964 KiB

jumps

#include <bits/stdc++.h>

#define f first
#define s second

#define ll long long

using namespace std;

const int mxN = 5e5 + 5;

int n, a[mxN];

vector <int> pos[mxN];

pair <int, int> t[mxN * 4];

void Build(int v = 1, int L = 1, int R = n) {
	if (L == R) {
		t[v] = {a[L], -1};
		return;
	}
	int M = (L + R) / 2;
	Build(v * 2, L, M);
	Build(v * 2 + 1, M + 1, R);
	if (t[v * 2].f >= t[v * 2 + 1].f)
		t[v] = {t[v * 2].f, max(t[v * 2].s, t[v * 2 + 1].f)};
	else
		t[v] = {t[v * 2 + 1].f, max(t[v * 2 + 1].s, t[v * 2].f)};
}

pair <int, int> Get(int l, int r, int v = 1, int L = 1, int R = n) {
	if (l <= L && R <= r)
		return t[v];
	if (l > R || r < L)
		return {-1, -1};
	int M = (L + R) / 2;
	auto left = Get(l, r, v * 2, L, M);
	auto right = Get(l, r, v * 2 + 1, M + 1, R);
	if (left.f >= right.f)
		return {left.f, max(left.s, right.f)};
	return {right.f, max(right.s, left.f)};
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	vector <int> vec;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		vec.push_back(a[i]);
	}
	sort(vec.begin(), vec.end());
	for (int i = 1; i <= n; ++i) {
		int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
		pos[x].push_back(i);
	}
	Build();
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		auto opt = Get(l, r);
		ll ans = 0;
		int x = lower_bound(vec.begin(), vec.end(), opt.f) - vec.begin();
		int y = lower_bound(vec.begin(), vec.end(), opt.s) - vec.begin();
		{ // max R <= r
			int R = pos[x][upper_bound(pos[x].begin(), pos[x].end(), r) - pos[x].begin() - 1];
			R = max(R, pos[y][upper_bound(pos[y].begin(), pos[y].end(), r) - pos[y].begin() - 1]);
			{ // middle, mid < R
				int mid;
				if (a[R] == opt.f) 
					mid = pos[y][lower_bound(pos[y].begin(), pos[y].end(), R) - pos[y].begin() - 1];
				else
					mid = pos[x][lower_bound(pos[x].begin(), pos[x].end(), R) - pos[x].begin() - 1];
				// now I should find optimal L
				int lb = max(l, mid - (R - mid)), rb = mid - 1;
				if (rb >= lb) 
					ans = 1ll * Get(lb, rb).f + opt.f + opt.s;
			}
			{ // min L >= l
				int L;
				if (a[R] == opt.f)
					L = pos[y][lower_bound(pos[y].begin(), pos[y].end(), l) - pos[y].begin()];
				else
					L = pos[x][lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin()];
				// now I should find optimal mid
				// R - mid >= mid - L
				// R + L >= 2 * mid
				int lb = L + 1, rb = (L + R) / 2;
				if (rb >= lb) 
					ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
			}
		}
		{ // min L >= l
			int L = pos[y][lower_bound(pos[y].begin(), pos[y].end(), l) - pos[y].begin()];
			L = min(L, pos[x][lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin()]);
			{ // middle, mid >= L
				int mid;
				if (a[L] == opt.f) 
					mid = pos[y][upper_bound(pos[y].begin(), pos[y].end(), L) - pos[y].begin()];
				else
					mid = pos[x][upper_bound(pos[x].begin(), pos[x].end(), L) - pos[x].begin()];
				// now I should find optimal 
				// R - mid >= L - mid
				int lb = mid + (mid - L), rb = r;
				if (rb >= lb) 
					ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
			}
			{ // max R <= r
				int R;
				if (a[R] == opt.f)
					R = pos[y][upper_bound(pos[y].begin(), pos[y].end(), r) - pos[y].begin() - 1];
				else
					R = pos[x][upper_bound(pos[x].begin(), pos[x].end(), r) - pos[x].begin() - 1];
				// now I should find optimal mid
				// R - mid >= mid - L
				// R + L >= 2 * mid
				int lb = L + 1, rb = (L + R) / 2;
				if (rb >= lb) 
					ans = max(ans, 1ll * Get(lb, rb).f + opt.f + opt.s);
			}
		}
		cout << ans << '\n';		
	}
	return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:113:12: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     if (a[R] == opt.f)
      |         ~~~^

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