Submission #1227704

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

edi

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 300000;

int aa[N + 1], hh[N + 1], dd[N + 1], pp[N + 1], qq[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 z; cin >> z;
		if (z > 0) {
			aa[i] = z;
			pp[i] = qq[i] = i;
		} else {
			hh[i] = -z;
			int p = i - 1;
			while (hh[p] >= hh[i])
				if (hh[qq[p]] >= hh[i])
					p = qq[p];
				else
					p = pp[p];
			p--;
			while (hh[p] >= hh[i])
				if (hh[qq[p]] >= hh[i])
					p = qq[p];
				else
					p = pp[p];
			dd[i] = dd[pp[i] = p] + 1;
			qq[i] = dd[p] - dd[qq[p]] == dd[qq[p]] - dd[qq[qq[p]]] ? qq[qq[p]] : p;
		}
		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