Submission #120137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120137	2019-06-23T14:11:45 Z	E869120	Editor (BOI15_edi)	C++14	100 / 100	706 ms	58656 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	11 ms	1280 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	12 ms	1408 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	11 ms	1280 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	11 ms	1280 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	525 ms	56656 KB	Output is correct
2	Correct	545 ms	57720 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	276 ms	28608 KB	Output is correct
2	Correct	335 ms	34980 KB	Output is correct
3	Correct	586 ms	45916 KB	Output is correct
4	Correct	535 ms	57720 KB	Output is correct
5	Correct	560 ms	58656 KB	Output is correct
6	Correct	582 ms	55712 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	11 ms	1280 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	12 ms	1408 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	11 ms	1280 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	11 ms	1280 KB	Output is correct
10	Correct	525 ms	56656 KB	Output is correct
11	Correct	545 ms	57720 KB	Output is correct
12	Correct	276 ms	28608 KB	Output is correct
13	Correct	335 ms	34980 KB	Output is correct
14	Correct	586 ms	45916 KB	Output is correct
15	Correct	535 ms	57720 KB	Output is correct
16	Correct	560 ms	58656 KB	Output is correct
17	Correct	582 ms	55712 KB	Output is correct
18	Correct	562 ms	58412 KB	Output is correct
19	Correct	549 ms	58276 KB	Output is correct
20	Correct	706 ms	57056 KB	Output is correct
21	Correct	521 ms	57864 KB	Output is correct
22	Correct	577 ms	58616 KB	Output is correct