Submission #120137

#	Time	Username	Problem	Language	Result	Execution time	Memory
120137		E869120	Editor (BOI15_edi)	C++14	100 / 100	706 ms	58656 KiB

edi

#include <iostream>
#include <algorithm>
using namespace std;

int N, A[1 << 19], dp[1 << 19][22], ret[1 << 19], dp2[1 << 19][22];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		if (A[i] > 0) { for (int j = 0; j <= 21; j++) { dp[i][j] = i; dp2[i][j] = 0; } ret[i] = A[i]; }
		else {
			int cx = i - 1, level = -A[i];
			for (int j = 21; j >= 0; j--) {
				if (dp2[cx][j] >= level) cx = dp[cx][j];
			}
			cx--;
			if (cx == 0) { ret[i] = 0; for (int j = 0; j <= 21; j++) dp2[i][j] = level; }
			else {
				ret[i] = ret[cx];
				dp[i][0] = cx; dp2[i][0] = level;
				for (int j = 1; j <= 21; j++) {
					dp[i][j] = dp[dp[i][j - 1]][j - 1];
					dp2[i][j] = min(dp2[i][j - 1], dp2[dp[i][j - 1]][j - 1]);
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) cout << ret[i] << endl;
	return 0;
}

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