Submission #713013

#	Time	Username	Problem	Language	Result	Execution time	Memory
713013		study	Editor (BOI15_edi)	C++17	100 / 100	113 ms	52520 KiB

edi

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

const int N = 3e5+1;

int pere[20][N], sufmin[20][N],res[N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i=1; i<=n; ++i){
		int a;
		cin >> a;
		if (a > 0){
			pere[0][i] = i;
			res[i] = a;
		}
		else{
			a = -a;
			int prev = i-1;
			for (int j=19; j>=0; --j){
				if (sufmin[j][prev] >= a) prev = pere[j][prev];
			}
			//if (prev != i-1) --prev;
			// undo operation prev
//			cout << "undo " << prev-1 << endl;

			res[i] = res[prev-1];
			pere[0][i] = prev-1;
			sufmin[0][i] = a;
		}
		for (int j=1; j<20; ++j){
			pere[j][i] = pere[j-1][pere[j-1][i]];
			sufmin[j][i] = min(sufmin[j-1][i],sufmin[j-1][pere[j-1][i]]);
		}
		cout << res[i] << '\n';
	}
	return 0;
}

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