Submission #712780

#	Time	Username	Problem	Language	Result	Execution time	Memory
712780		study	Editor (BOI15_edi)	C++17	0 / 100	2 ms	852 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[i][0] = 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];
			}
			// undo operation prev
			// cout << "undo " << prev-1 << endl;
			res[i] = res[prev-1];
			pere[0][i] = res[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][sufmin[j-1][i]]);
			}
		}
		cout << res[i] << '\n';
	}
	return 0;
}

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