oj.uz

Submission #210308

# Submission time Handle Problem Language Result Execution time Memory
210308 2020-03-17T02:57:38 Z Seanliu Xylophone (JOI18_xylophone) C++14
0 / 100
 5 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Incorrect 5 ms 376 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Incorrect 5 ms 376 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 248 KB Output is correct
3 Incorrect 5 ms 376 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -