제출 #1156611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156611		Pwo	popa (BOI18_popa)	C++20	100 / 100	25 ms	468 KiB

popa

#include <bits/stdc++.h>
#include "popa.h"
using namespace std;

int nxt[1005]; vector<int> st;
int lo[1005], hi[1005];

int query(int a, int b, int c, int d);

int build(int l, int r) {
	if (l > r) return -1;
	int rt = l;
	while (nxt[rt] <= r) rt = nxt[rt];
	lo[rt] = build(l, rt - 1);
	hi[rt] = build(rt + 1, r);
	return rt;
}

int solve(int N, int* left, int* right) {
	for (int i = 0; i < N; i++) {
		while (!st.empty() && query(i, i, st.back(), i)) {
			nxt[st.back()] = i;
			st.pop_back();
		}
		st.push_back(i);
	}
	while (!st.empty()) {
		nxt[st.back()] = 1e5;
		st.pop_back();
	}
	
	int rt = build(0, N - 1);
	for (int i = 0; i < N; i++) left[i] = lo[i], right[i] = hi[i];
	return rt;
}

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