Submission #1227707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227707		kaiboy	Editor (BOI15_edi)	C++20	100 / 100	34 ms	8300 KiB

edi

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 300000;

int aa[N + 1], hh[N + 1], pp[N + 1], qq[N + 1], ll[N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		int b; cin >> b;
		if (b > 0)
			aa[i] = b, pp[i] = qq[i] = i;
		else {
			hh[i] = -b;
			int p = i;
			for (int z = 0; z < 2; z++)
				for (p--; hh[p] >= hh[i]; )
					if (hh[qq[p]] >= hh[i])
						p = qq[p];
					else
						p = pp[p];
			pp[i] = p;
			if (ll[p] == ll[qq[p]])
				qq[i] = qq[qq[p]], ll[i] = ll[p] + 1;
			else
				qq[i] = p, ll[i] = 1;
		}
		int p = i;
		while (pp[p] < p)
			p = qq[p];
		cout << aa[p] << '\n';
	}
	return 0;
}

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