제출 #1180368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180368		xnqs	Editor (BOI15_edi)	C++20	100 / 100	97 ms	26952 KiB

edi

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int q;
int state[300005];
int level[300005];
int up[19][300005];

int search_ancestor(int node, int max_level) {
	if (level[node] <= max_level) {
		return node;
	}

	for (int lvl = 18; lvl >= 0; lvl--) {
		if (level[up[lvl][node]] > max_level) {
			node = up[lvl][node];
		}
	}

	return up[0][node];
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> q;
	for (int i = 1; i <= q; i++) {
		std::cin >> state[i];
		level[i] = 0;
		if (state[i]<0) {
			level[i] = -state[i];

			int p = search_ancestor(i-1, level[i]-1);
			up[0][i] = search_ancestor(p-1, level[i]-1);
			for (int j = 1; j < 19; j++) {
				up[j][i] = up[j-1][up[j-1][i]];
			}
		}

		std::cout << state[search_ancestor(i, 0)] << "\n";
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37