Submission #110971

#	Time	Username	Problem	Language	Result	Execution time	Memory
110971		tjd229	popa (BOI18_popa)	C++14	100 / 100	89 ms	428 KiB

popa

#include "popa.h"
#include <stack>
using namespace std;
int solve(int N, int *Left, int *Right) {
	*Left = -1, *Right = -1;
	stack<int> stk; stk.push(0);
	int root = 0;
	for (int i = 1; i < N; ++i) {
		Left[i] = Right[i] = -1;
		while (stk.size() && query(i,i,stk.top(),i)) {
			//Right[stk.top()] = Left[i];
			Left[i] = stk.top();
			stk.pop();
		}
		if (stk.size()) Right[stk.top()] = i;
		else root = i;
		stk.push(i);
	}
	return root;
}

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39