Submission #210308

#	Time	Username	Problem	Language	Result	Execution time	Memory
210308		Seanliu	Xylophone (JOI18_xylophone)	C++14	0 / 100	5 ms	376 KiB

xylophone

#include <iostream>
#include "xylophone.h"
using namespace std;

const int maxN = 6e3 + 226;

int val[maxN], abd[maxN];

void solve(int N){
	int maxAt, l = 0, r = N, m;
	while(l + 1 < r){
		m = (l + r) / 2;
		if(query(1, m) == N - 1){
			r = m;	
		} else {
			l = m;
		}
	}
	maxAt = r;
	val[maxAt] = N;
	
	//cout << "Maxat = " << maxAt << endl;
	if(maxAt < N){
		val[maxAt + 1] = N - query(maxAt, maxAt + 1);
		//cout << "val[" << maxAt + 1 << "] = " << val[maxAt + 1] << endl;
	}
	if(maxAt > 1){
		val[maxAt - 1] = N - query(maxAt - 1, maxAt);
		//cout << "val[" << maxAt - 1 << "] = " << val[maxAt - 1] << endl;
	}	
	int currentEx = maxAt, cur = N - val[maxAt + 1], type = -1; //-1: currently at maxima, else currently at minima
	for(int i = maxAt + 2; i <= N; i++){
		int r = query(currentEx, i);
		if(r > cur){
			val[i] = val[currentEx] + type * r;		
			cur = r;
		} else {
			currentEx = i - 1;	
			type *= -1;
			cur = r = query(currentEx, i);
			val[i] = val[currentEx] + type * r;
		}
	}
	currentEx = maxAt, cur = N - val[maxAt - 1], type = -1;
	for(int i = maxAt - 2; i; i--){
		int r = query(i, currentEx);
		//cout << "currentEx = " << currentEx << ", i = " << i << ", r = " << r << endl;
		if(r > cur){
			val[i] = val[currentEx] + type * r;		
			cur = r;
		} else {
			currentEx = i + 1;	
			type *= -1;
			cur = r = query(i, currentEx);
			val[i] = val[currentEx] + type * r;
		}
	}
	for(int i = 1; i <= N; i++){
		//cout << "val[" << i << "] = " << val[i] << endl;
		answer(i, val[i]);
	}
}

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