oj.uz

Submission #525456

# Submission time Handle Problem Language Result Execution time Memory
525456 2022-02-11T17:07:34 Z rainboy 즐거운 사진 수집 (JOI13_collecting) C
100 / 100
 1143 ms 61900 KB 
#include <stdio.h>

#define H_	20
#define N_	(1 << H_)

int h_, n_;

void pul(int *st, int *kk, int i, int h) {
	int l = i << 1, r = l | 1;

	if (st[i] != -1)
		kk[h]--;
	st[i] = st[l] == -1 || st[r] == -1 || st[l] != st[r] ? -1 : st[l];
	if (st[i] != -1)
		kk[h]++;
}

void update(int *st, int *kk, int i) {
	int h;

	i += n_;
	st[i] ^= 1;
	for (h = 1; h <= h_; h++)
		pul(st, kk, i >> h, h);
}

int main() {
	static int st1[N_ * 2], st2[N_ * 2], kk1[H_ + 1], kk2[H_ + 1];
	int q, h;

	scanf("%d%d", &h_, &q), n_ = 1 << h_;
	for (h = 0; h <= h_; h++)
		kk1[h] = kk2[h] = n_ >> h;
	while (q--) {
		int t, h, i, j;
		long long ans;

		scanf("%d", &t);
		if (t == 0) {
			scanf("%d", &i), i--;
			update(st1, kk1, i);
		} else {
			scanf("%d", &j), j--;
			update(st2, kk2, j);
		}
		ans = 0;
		for (h = 0; h <= h_; h++)
			ans += (long long) (n_ >> h) * (n_ >> h) - (long long) kk1[h] * kk2[h];
		ans = ans * 4 + 1;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

collecting.c: In function 'main':
collecting.c:31:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d", &h_, &q), n_ = 1 << h_;
      |  ^~~~~~~~~~~~~~~~~~~~~~
collecting.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
collecting.c:40:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
collecting.c:43:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 61656 KB Output is correct
2 Correct 1076 ms 61572 KB Output is correct
3 Correct 926 ms 50512 KB Output is correct
4 Correct 1056 ms 61900 KB Output is correct
5 Correct 1092 ms 61396 KB Output is correct
6 Correct 1030 ms 60332 KB Output is correct
7 Correct 1143 ms 61464 KB Output is correct
8 Correct 1076 ms 61524 KB Output is correct
9 Correct 895 ms 49184 KB Output is correct
10 Correct 963 ms 51752 KB Output is correct
11 Correct 1033 ms 60208 KB Output is correct
12 Correct 1039 ms 60220 KB Output is correct
13 Correct 944 ms 51632 KB Output is correct