Submission #340143

#	Time	Username	Problem	Language	Result	Execution time	Memory
340143		8e7	Editor (BOI15_edi)	C++14	100 / 100	187 ms	29036 KiB

edi

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#define maxn 300005
using namespace std;
int anc[19][maxn], lev[maxn], a[maxn];
inline int getpar(int x, int hei) {
	if (lev[x] <= hei) return x;
	for (int i = 18;i >= 0;i--) {
		if (lev[anc[i][x]] > hei) x = anc[i][x];
	}
	return anc[0][x];
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) {
		int x;
		cin >> x;
		if (x < 0) {
			lev[i] = -x;
			int z = getpar(i - 1, lev[i] - 1);
			anc[0][i] = getpar(z - 1, lev[i] - 1);
			for (int j = 1;j < 19;j++) anc[j][i] = anc[j - 1][anc[j - 1][i]];
		} else {
			a[i] = x;
		}
		cout << a[getpar(i, 0)] << "\n";
	}
}

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