oj.uz

Submission #745304

# Submission time Handle Problem Language Result Execution time Memory
745304 2023-05-19T19:20:20 Z rainboy I want to be the very best too! (NOI17_pokemonmaster) C
100 / 100
 2524 ms 11880 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	50000
#define C	50000
#define Q	100000
#define B	36	/* B = floor(cbrt(N)) */

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N];

int compare_a(int i, int j) { return aa[i] - aa[j]; }

int tt[Q], ii_[Q], xx[Q], ll[Q], rr[Q];

int compare_hlr(int h1, int h2) {
	if (h1 / B != h2 / B)
		return h1 / B - h2 / B;
	if (ll[h1] / B != ll[h2] / B)
		return ll[h1] / B - ll[h2] / B;
	return rr[h1] - rr[h2];
}

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ds[N], ww[N], *ej[N], *ew[N], eo[N];

void append(int i, int j, int w) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}

void join(int i, int j, int w) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, ww[i] = w, append(j, i, w);
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, ww[j] = w, append(i, j, w);
	}
}

int ta[N], tb[N];

void dfs(int i) {
	static int time;
	int o;

	ta[i] = time++;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		dfs(j);
	}
	tb[i] = time;
}

void get_interval(int i, int w, int *l, int *r) {
	int lower, upper, o;

	while (ww[i] <= w)
		i = ds[i];
	*l = ta[i];
	lower = -1, upper = eo[i];
	while (upper - lower > 1) {
		o = (lower + upper) / 2;
		if (ew[i][o] <= w)
			lower = o;
		else
			upper = o;
	}
	*r = lower == -1 ? ta[i] + 1 : tb[ej[i][lower]];
}

int cc[N]; int kk[C + 1], h_, l_, r_, cnt;

void incr(int c) {
	if (kk[c]++ == 0)
		cnt++;
}

void decr(int c) {
	if (--kk[c] == 0)
		cnt--;
}

int main() {
	static int ii[N], hh[Q], ans[Q];
	static char marked[N];
	int nm, n, m, q, q_, g, h, i, i_, j_, x, y, a, c;

	scanf("%d%d%d", &n, &m, &q), nm = n * m;
	for (i = 0; i < nm; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < nm; i++)
		ii[i] = i;
	compare = compare_a, sort(ii, 0, nm);
	memset(ds, -1, nm * sizeof *ds), memset(ww, 0x3f, nm * sizeof *ww);
	for (i = 0; i < nm; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (int *) malloc(2 * sizeof *ew[i]);
	}
	for (i = 0; i < nm; i++) {
		i_ = ii[i], x = i_ / m, y = i_ % m;
		marked[i_] = 1;
		if (x > 0 && marked[j_ = (x - 1) * m + y])
			join(i_, j_, aa[i_]);
		if (x + 1 < n && marked[j_ = (x + 1) * m + y])
			join(i_, j_, aa[i_]);
		if (y > 0 && marked[j_ = x * m + (y - 1)])
			join(i_, j_, aa[i_]);
		if (y + 1 < m && marked[j_ = x * m + (y + 1)])
			join(i_, j_, aa[i_]);
	}
	dfs(find(0));
	for (i = 0; i < nm; i++)
		scanf("%d", &cc[ta[i]]);
	for (h = 0; h < q; h++) {
		scanf("%d%d%d", &tt[h], &y, &x), y--, x--, i = x * m + y;
		if (tt[h] == 1) {
			scanf("%d", &c);
			ii_[h] = ta[i], xx[h] = c ^ cc[ta[i]];
			cc[ta[i]] = c;
		} else {
			scanf("%d", &a);
			if (aa[i] > a)
				ll[h] = rr[h] = 0;
			else
				get_interval(i, a, &ll[h], &rr[h]);
		}
	}
	q_ = 0;
	for (h = 0; h < q; h++)
		if (tt[h] == 1)
			cc[ii_[h]] ^= xx[h];
		else
			hh[q_++] = h;
	compare = compare_hlr, sort(hh, 0, q_);
	h_ = -1, l_ = 0, r_ = 0;
	for (g = 0; g < q_; g++) {
		h = hh[g];
		while (h_ < h) {
			h_++;
			if (tt[h_] == 1) {
				i = ii_[h_];
				if (l_ <= i && i < r_)
					decr(cc[i]);
				cc[i] ^= xx[h_];
				if (l_ <= i && i < r_)
					incr(cc[i]);
			}
		}
		while (h_ > h) {
			if (tt[h_] == 1) {
				i = ii_[h_];
				if (l_ <= i && i < r_)
					decr(cc[i]);
				cc[i] ^= xx[h_];
				if (l_ <= i && i < r_)
					incr(cc[i]);
			}
			h_--;
		}
		while (l_ > ll[h])
			incr(cc[--l_]);
		while (r_ < rr[h])
			incr(cc[r_++]);
		while (l_ < ll[h])
			decr(cc[l_++]);
		while (r_ > rr[h])
			decr(cc[--r_]);
		ans[h] = cnt;
	}
	for (h = 0; h < q; h++)
		if (tt[h] == 2)
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message

pokemonmaster.c: In function 'append':
pokemonmaster.c:59:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   59 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
pokemonmaster.c: In function 'main':
pokemonmaster.c:133:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |  scanf("%d%d%d", &n, &m, &q), nm = n * m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:135:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
pokemonmaster.c:158:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |   scanf("%d", &cc[ta[i]]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:160:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |   scanf("%d%d%d", &tt[h], &y, &x), y--, x--, i = x * m + y;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:162:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |    scanf("%d", &c);
      |    ^~~~~~~~~~~~~~~
pokemonmaster.c:166:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |    scanf("%d", &a);
      |    ^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6772 KB Output is correct
2 Correct 27 ms 6896 KB Output is correct
3 Correct 29 ms 6872 KB Output is correct
4 Correct 27 ms 6780 KB Output is correct
5 Correct 36 ms 6968 KB Output is correct
6 Correct 31 ms 6880 KB Output is correct
7 Correct 26 ms 6688 KB Output is correct
8 Correct 28 ms 6924 KB Output is correct
9 Correct 27 ms 6776 KB Output is correct
10 Correct 31 ms 6964 KB Output is correct
11 Correct 28 ms 6968 KB Output is correct
12 Correct 35 ms 6904 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7080 KB Output is correct
2 Correct 25 ms 7312 KB Output is correct
3 Correct 23 ms 7296 KB Output is correct
4 Correct 24 ms 6932 KB Output is correct
5 Correct 22 ms 7020 KB Output is correct
6 Correct 21 ms 6992 KB Output is correct
7 Correct 29 ms 7200 KB Output is correct
8 Correct 28 ms 7372 KB Output is correct
9 Correct 27 ms 7208 KB Output is correct
10 Correct 27 ms 7356 KB Output is correct
11 Correct 29 ms 7412 KB Output is correct
12 Correct 32 ms 7460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1544 ms 11584 KB Output is correct
2 Correct 1247 ms 10988 KB Output is correct
3 Correct 889 ms 10516 KB Output is correct
4 Correct 670 ms 10372 KB Output is correct
5 Correct 801 ms 10976 KB Output is correct
6 Correct 819 ms 11336 KB Output is correct
7 Correct 1239 ms 11144 KB Output is correct
8 Correct 1230 ms 11212 KB Output is correct
9 Correct 1238 ms 11088 KB Output is correct
10 Correct 1218 ms 11068 KB Output is correct
11 Correct 1250 ms 11144 KB Output is correct
12 Correct 1297 ms 11096 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6772 KB Output is correct
2 Correct 27 ms 6896 KB Output is correct
3 Correct 29 ms 6872 KB Output is correct
4 Correct 27 ms 6780 KB Output is correct
5 Correct 36 ms 6968 KB Output is correct
6 Correct 31 ms 6880 KB Output is correct
7 Correct 26 ms 6688 KB Output is correct
8 Correct 28 ms 6924 KB Output is correct
9 Correct 27 ms 6776 KB Output is correct
10 Correct 31 ms 6964 KB Output is correct
11 Correct 28 ms 6968 KB Output is correct
12 Correct 35 ms 6904 KB Output is correct
13 Correct 811 ms 11044 KB Output is correct
14 Correct 808 ms 11280 KB Output is correct
15 Correct 885 ms 10844 KB Output is correct
16 Correct 651 ms 10664 KB Output is correct
17 Correct 803 ms 11136 KB Output is correct
18 Correct 1039 ms 11552 KB Output is correct
19 Correct 854 ms 10936 KB Output is correct
20 Correct 811 ms 11056 KB Output is correct
21 Correct 810 ms 10824 KB Output is correct
22 Correct 1101 ms 11116 KB Output is correct
23 Correct 833 ms 11096 KB Output is correct
24 Correct 1561 ms 11232 KB Output is correct

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6772 KB Output is correct
2 Correct 27 ms 6896 KB Output is correct
3 Correct 29 ms 6872 KB Output is correct
4 Correct 27 ms 6780 KB Output is correct
5 Correct 36 ms 6968 KB Output is correct
6 Correct 31 ms 6880 KB Output is correct
7 Correct 26 ms 6688 KB Output is correct
8 Correct 28 ms 6924 KB Output is correct
9 Correct 27 ms 6776 KB Output is correct
10 Correct 31 ms 6964 KB Output is correct
11 Correct 28 ms 6968 KB Output is correct
12 Correct 35 ms 6904 KB Output is correct
13 Correct 23 ms 7080 KB Output is correct
14 Correct 25 ms 7312 KB Output is correct
15 Correct 23 ms 7296 KB Output is correct
16 Correct 24 ms 6932 KB Output is correct
17 Correct 22 ms 7020 KB Output is correct
18 Correct 21 ms 6992 KB Output is correct
19 Correct 29 ms 7200 KB Output is correct
20 Correct 28 ms 7372 KB Output is correct
21 Correct 27 ms 7208 KB Output is correct
22 Correct 27 ms 7356 KB Output is correct
23 Correct 29 ms 7412 KB Output is correct
24 Correct 32 ms 7460 KB Output is correct
25 Correct 1544 ms 11584 KB Output is correct
26 Correct 1247 ms 10988 KB Output is correct
27 Correct 889 ms 10516 KB Output is correct
28 Correct 670 ms 10372 KB Output is correct
29 Correct 801 ms 10976 KB Output is correct
30 Correct 819 ms 11336 KB Output is correct
31 Correct 1239 ms 11144 KB Output is correct
32 Correct 1230 ms 11212 KB Output is correct
33 Correct 1238 ms 11088 KB Output is correct
34 Correct 1218 ms 11068 KB Output is correct
35 Correct 1250 ms 11144 KB Output is correct
36 Correct 1297 ms 11096 KB Output is correct
37 Correct 811 ms 11044 KB Output is correct
38 Correct 808 ms 11280 KB Output is correct
39 Correct 885 ms 10844 KB Output is correct
40 Correct 651 ms 10664 KB Output is correct
41 Correct 803 ms 11136 KB Output is correct
42 Correct 1039 ms 11552 KB Output is correct
43 Correct 854 ms 10936 KB Output is correct
44 Correct 811 ms 11056 KB Output is correct
45 Correct 810 ms 10824 KB Output is correct
46 Correct 1101 ms 11116 KB Output is correct
47 Correct 833 ms 11096 KB Output is correct
48 Correct 1561 ms 11232 KB Output is correct
49 Correct 1575 ms 11828 KB Output is correct
50 Correct 1335 ms 11812 KB Output is correct
51 Correct 1124 ms 11264 KB Output is correct
52 Correct 665 ms 10844 KB Output is correct
53 Correct 818 ms 11484 KB Output is correct
54 Correct 1087 ms 11880 KB Output is correct
55 Correct 1323 ms 11480 KB Output is correct
56 Correct 1256 ms 11592 KB Output is correct
57 Correct 1242 ms 11492 KB Output is correct
58 Correct 1751 ms 11760 KB Output is correct
59 Correct 1261 ms 11688 KB Output is correct
60 Correct 2524 ms 11688 KB Output is correct