Submission #745287

#	Time	Username	Problem	Language	Result	Execution time	Memory
745287		rainboy	I want to be the very best too! (NOI17_pokemonmaster)	C11	47 / 100	5080 ms	110912 KiB

pokemonmaster

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	50000
#define Q	100000
#define LN	16	/* LN = ceil(log2(N)) */
#define N_	(1 << LN)
#define N1	(N + Q + (N + Q * 3) * (LN + 1) + 1)

unsigned int X = 12345;

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

int aa[N];

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)
			if (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[i_]) {
				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 zz[N1], ll[N1], rr[N1], ii_[N1], sz[N1], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii_[_] = i, sz[_] = 1;
	return _++;
}

void pul(int u) {
	sz[u] = sz[ll[u]] + 1 + sz[rr[u]];
}

int mode;

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = mode == 0 && cc[ii_[u]] != cc[i] ? cc[ii_[u]] - cc[i] : ii_[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int tr_query(int u, int i) {
	int k = 0;

	while (u)
		if (ii_[u] < i)
			k += sz[u] - sz[rr[u]], u = rr[u];
		else
			u = ll[u];
	return k;
}

int uu[N_ * 2], n_;

void st_add(int i, int j) {
	mode = 1;
	for (i += n_; i > 0; i >>= 1) {
		split(uu[i], j);
		uu[i] = merge(merge(l_, node(j)), r_);
	}
}

void st_remove(int i, int j) {
	mode = 1;
	for (i += n_; i > 0; i >>= 1) {
		split(uu[i], j);
		uu[i] = merge(l_, r_);
	}
}

int st_query(int l, int j) {
	int r = n_ - 1, k = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1)
			k += tr_query(uu[l++], j);
	return k;
}

int u1;

void add(int i) {
	int p, q;

	mode = 0, split(u1, i);
	p = l_ == 0 ? -1 : ii_[last(l_)], q = r_ == 0 ? -1 : ii_[first(r_)];
	u1 = merge(merge(l_, node(i)), r_);
	if (p != -1 && q != -1 && cc[p] == cc[q])
		st_remove(p, q);
	if (p != -1 && cc[p] == cc[i])
		st_add(p, i);
	if (q != -1 && cc[i] == cc[q])
		st_add(i, q);
}

void remove_(int i) {
	int p, q;

	mode = 0, split(u1, i);
	p = l_ == 0 ? -1 : ii_[last(l_)], q = r_ == 0 ? -1 : ii_[first(r_)];
	u1 = merge(l_, r_);
	if (p != -1 && cc[p] == cc[i])
		st_remove(p, i);
	if (q != -1 && cc[i] == cc[q])
		st_remove(i, q);
	if (p != -1 && q != -1 && cc[p] == cc[q])
		st_add(p, q);
}

int main() {
	static int ii[N];
	static char marked[N];
	int nm, n, m, q, i, i_, j_, x, y;

	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;
	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]]);
	n_ = 1;
	while (n_ < nm)
		n_ <<= 1;
	for (i = 0; i < nm; i++)
		add(i);
	while (q--) {
		int t;

		scanf("%d%d%d", &t, &y, &x), y--, x--, i = x * m + y;
		if (t == 1) {
			remove_(ta[i]);
			scanf("%d", &cc[ta[i]]);
			add(ta[i]);
		} else {
			int a, l, r;

			scanf("%d", &a);
			if (aa[i] > a) {
				printf("0\n");
				continue;
			}
			get_interval(i, a, &l, &r);
			printf("%d\n", r - l - st_query(l, r));
		}
	}
	return 0;
}

Compilation message (stderr)

pokemonmaster.c: In function 'append':
pokemonmaster.c:43:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   43 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
pokemonmaster.c: In function 'main':
pokemonmaster.c:233:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |  scanf("%d%d%d", &n, &m, &q), nm = n * m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:235:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
pokemonmaster.c:258:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |   scanf("%d", &cc[ta[i]]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:267:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |   scanf("%d%d%d", &t, &y, &x), y--, x--, i = x * m + y;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:270:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  270 |    scanf("%d", &cc[ta[i]]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~
pokemonmaster.c:275:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |    scanf("%d", &a);
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 29