Submission #745304

#	Time	Username	Problem	Language	Result	Execution time	Memory
745304		rainboy	I want to be the very best too! (NOI17_pokemonmaster)	C11	100 / 100	2524 ms	11880 KiB

pokemonmaster

#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 (stderr)

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 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29