oj.uz

Submission #199687

# Submission time Handle Problem Language Result Execution time Memory
199687 2020-02-02T18:47:46 Z dolphingarlic Editor (BOI15_edi) C++14
100 / 100
 288 ms 50552 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int anc[300001][20], mn[300001][20], ans[300001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	FOR(i, 1, n + 1) {
		int x;
		cin >> x;
		if (x > 0) {
			ans[i] = x;
			anc[i][0] = i;
		} else {
			x = -x;
			int curr = i - 1;
			for (int j = 19; ~j; j--) if (mn[curr][j] >= x) curr = anc[curr][j];
			anc[i][0] = curr - 1;
			ans[i] = ans[curr - 1];
			mn[i][0] = x;
			FOR(j, 1, 20) {
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
				mn[i][j] = min(mn[i][j - 1], mn[anc[i][j - 1]][j - 1]);
			}
		}
	}
	FOR(i, 1, n + 1) cout << ans[i] << '\n';
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 7 ms 1144 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 7 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 50552 KB Output is correct
2 Correct 113 ms 50472 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19448 KB Output is correct
2 Correct 64 ms 23288 KB Output is correct
3 Correct 218 ms 39388 KB Output is correct
4 Correct 111 ms 50552 KB Output is correct
5 Correct 123 ms 50552 KB Output is correct
6 Correct 155 ms 49020 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 7 ms 1144 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 7 ms 1144 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 7 ms 1144 KB Output is correct
10 Correct 113 ms 50552 KB Output is correct
11 Correct 113 ms 50472 KB Output is correct
12 Correct 56 ms 19448 KB Output is correct
13 Correct 64 ms 23288 KB Output is correct
14 Correct 218 ms 39388 KB Output is correct
15 Correct 111 ms 50552 KB Output is correct
16 Correct 123 ms 50552 KB Output is correct
17 Correct 155 ms 49020 KB Output is correct
18 Correct 110 ms 38780 KB Output is correct
19 Correct 116 ms 38752 KB Output is correct
20 Correct 288 ms 49272 KB Output is correct
21 Correct 114 ms 50424 KB Output is correct
22 Correct 128 ms 50424 KB Output is correct