Submission #780896

#	Time	Username	Problem	Language	Result	Execution time	Memory
780896		JoenPoenMan	Xylophone (JOI18_xylophone)	C++17	47 / 100	85 ms	960 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;

map<ii, int> queries;

int q(int l, int h) {
	if (l == h) return 0;
	if (queries.find({l, h}) != queries.end()) {
		return queries[{l, h}];
	}
	int res = query(l, h);
	queries[{l, h}] = res;
	return res;
}

void findNext2(int N, int top, int bot, int prevPitch, bool MIN);

void findNext1(int N, int top, int bot = 1, int prevPitch = 1, bool MIN = false, bool exl = false) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int diff = q(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high)/2;
			int res = q(bot, mid);
			if (res == diff) high = mid;
			else low = mid+1;
		}
	} else low = top;
	answer(low, prevPitch+diff*(MIN?-1:1));
	findNext1(N, top, low, prevPitch+diff*(MIN?-1:1), !MIN, true);
	findNext2(N, low, bot + exl, prevPitch+diff*(MIN?-1:1), !MIN);
}

void findNext2(int N, int top, int bot, int prevPitch, bool MIN ) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int diff = q(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high+1)/2;
			int res = q(mid, top);
			if (res == diff) low = mid;
			else high = mid-1;
		}
	} else low = bot;
	answer(low, prevPitch+diff*(MIN?-1:1));
	findNext1(N, top-1, low, prevPitch+diff*(MIN?-1:1), !MIN, true);
	findNext2(N, low, bot, prevPitch+diff*(MIN?-1:1), !MIN);
}

void solve(int N) {
	findNext1(N, N);
}

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53