Submission #544719

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544719	2022-04-02T16:09:22 Z	rainboy	Editor (BOI15_edi)	C	100 / 100	230 ms	51276 KB

edi

/* upsolve after reading analysis */
#include <stdio.h>

#define N	300000
#define L	18	/* L = pow2(log2(N - 1)) */

int min(int a, int b) { return a < b ? a : b; }

int main() {
	static int aa[N], pp[N][L + 1], aa_[N][L + 1], ll[N], ans[N];
	int n, i, l;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int a;

		scanf("%d", &a);
		if (a > 0) {
			aa[i] = 0, ans[i] = a;
			pp[i][0] = i - 1, aa_[i][0] = aa[i];
			for (l = 0; pp[i][l] != -1; l++) {
				int p = pp[i][l];

				pp[i][l + 1] = pp[p][l];
				aa_[i][l + 1] = min(aa_[i][l], aa_[p][l]);
			}
			ll[i] = l;
		} else {
			int p;

			aa[i] = -a;
			for (p = i - 1, l = ll[p]; l >= 0; l--)
				if (l <= ll[p] && aa[i] <= aa_[p][l])
					p = pp[p][l];
			p--;
			ans[i] = p == -1 ? 0 : ans[p];
			pp[i][0] = p, aa_[i][0] = aa[i];
			for (l = 0; (p = pp[i][l]) != -1; l++) {
				pp[i][l + 1] = pp[p][l];
				aa_[i][l + 1] = min(aa_[i][l], aa_[p][l]);
			}
			ll[i] = l;
		}
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message

edi.c: In function 'main':
edi.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
edi.c:17:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%d", &a);
      |   ^~~~~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	1108 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	3 ms	1072 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	1108 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	2 ms	1072 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	50648 KB	Output is correct
2	Correct	118 ms	50620 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	25520 KB	Output is correct
2	Correct	82 ms	30576 KB	Output is correct
3	Correct	171 ms	39960 KB	Output is correct
4	Correct	118 ms	50604 KB	Output is correct
5	Correct	159 ms	51272 KB	Output is correct
6	Correct	134 ms	48484 KB	Output is correct

Subtask #4

37.0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	1108 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	3 ms	1072 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	1108 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	2 ms	1072 KB	Output is correct
10	Correct	113 ms	50648 KB	Output is correct
11	Correct	118 ms	50620 KB	Output is correct
12	Correct	73 ms	25520 KB	Output is correct
13	Correct	82 ms	30576 KB	Output is correct
14	Correct	171 ms	39960 KB	Output is correct
15	Correct	118 ms	50604 KB	Output is correct
16	Correct	159 ms	51272 KB	Output is correct
17	Correct	134 ms	48484 KB	Output is correct
18	Correct	135 ms	51256 KB	Output is correct
19	Correct	141 ms	51052 KB	Output is correct
20	Correct	230 ms	49808 KB	Output is correct
21	Correct	112 ms	50636 KB	Output is correct
22	Correct	169 ms	51276 KB	Output is correct