Submission #1130797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130797		idiotcomputer	Editor (BOI15_edi)	C++20	100 / 100	103 ms	28232 KiB

edi

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

const int mxN = 3e5+5;

int p[mxN][20];
int l[mxN];
int v[mxN];
int getp(int i, int t){
	//first parent of i with level < t
	while (l[i] >= t){
		for (int j = 1; j < 20; j++){
			if (l[p[i][j]] < t){ i = p[i][j-1]; break;}
		}
	}
	return i;
}

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

	int n;
	cin >> n;

	l[0] = -1;
	memset(p,0,sizeof(p));

	int c;
	for (int i = 1; i <= n; i++){
		cin >> c;
		if (c > 0){
			l[i] = 0;
			v[i] = c; 
			cout << c << '\n';
		} else {
			c=-c;
			l[i] = c;
			int idx = getp(i-1,c);
			idx = getp(idx-1,c);
			for (int j = 0; idx > 0, j < 20; j++){
				p[i][j] = idx;
				idx = p[idx][j];
			}
			cout << v[getp(i,1)] << '\n';
		}
	}
	return 0;
}

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