답안 #745287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745287	2023-05-19T18:48:50 Z	rainboy	I want to be the very best too! (NOI17_pokemonmaster)	C	47 / 100	5000 ms	110912 KB

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

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	24764 KB	Output is correct
2	Correct	166 ms	25132 KB	Output is correct
3	Correct	228 ms	23840 KB	Output is correct
4	Correct	142 ms	25572 KB	Output is correct
5	Correct	165 ms	25168 KB	Output is correct
6	Correct	175 ms	23108 KB	Output is correct
7	Correct	115 ms	25248 KB	Output is correct
8	Correct	149 ms	25228 KB	Output is correct
9	Correct	125 ms	25216 KB	Output is correct
10	Correct	203 ms	23416 KB	Output is correct
11	Correct	168 ms	25112 KB	Output is correct
12	Correct	158 ms	19020 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	25116 KB	Output is correct
2	Correct	153 ms	24984 KB	Output is correct
3	Correct	179 ms	23344 KB	Output is correct
4	Correct	128 ms	24884 KB	Output is correct
5	Correct	144 ms	24796 KB	Output is correct
6	Correct	166 ms	22444 KB	Output is correct
7	Correct	108 ms	25296 KB	Output is correct
8	Correct	143 ms	25188 KB	Output is correct
9	Correct	130 ms	25112 KB	Output is correct
10	Correct	177 ms	23376 KB	Output is correct
11	Correct	155 ms	25024 KB	Output is correct
12	Correct	166 ms	19236 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	493 ms	33792 KB	Output is correct
2	Correct	2139 ms	77632 KB	Output is correct
3	Correct	3345 ms	110912 KB	Output is correct
4	Correct	3376 ms	110568 KB	Output is correct
5	Correct	2077 ms	77308 KB	Output is correct
6	Correct	468 ms	32968 KB	Output is correct
7	Correct	2130 ms	77500 KB	Output is correct
8	Correct	2112 ms	77640 KB	Output is correct
9	Correct	2140 ms	77688 KB	Output is correct
10	Correct	2121 ms	77680 KB	Output is correct
11	Correct	2138 ms	77396 KB	Output is correct
12	Correct	2177 ms	77468 KB	Output is correct

Subtask #4

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	24764 KB	Output is correct
2	Correct	166 ms	25132 KB	Output is correct
3	Correct	228 ms	23840 KB	Output is correct
4	Correct	142 ms	25572 KB	Output is correct
5	Correct	165 ms	25168 KB	Output is correct
6	Correct	175 ms	23108 KB	Output is correct
7	Correct	115 ms	25248 KB	Output is correct
8	Correct	149 ms	25228 KB	Output is correct
9	Correct	125 ms	25216 KB	Output is correct
10	Correct	203 ms	23416 KB	Output is correct
11	Correct	168 ms	25112 KB	Output is correct
12	Correct	158 ms	19020 KB	Output is correct
13	Correct	471 ms	33084 KB	Output is correct
14	Correct	3164 ms	76700 KB	Output is correct
15	Execution timed out	5080 ms	80456 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	24764 KB	Output is correct
2	Correct	166 ms	25132 KB	Output is correct
3	Correct	228 ms	23840 KB	Output is correct
4	Correct	142 ms	25572 KB	Output is correct
5	Correct	165 ms	25168 KB	Output is correct
6	Correct	175 ms	23108 KB	Output is correct
7	Correct	115 ms	25248 KB	Output is correct
8	Correct	149 ms	25228 KB	Output is correct
9	Correct	125 ms	25216 KB	Output is correct
10	Correct	203 ms	23416 KB	Output is correct
11	Correct	168 ms	25112 KB	Output is correct
12	Correct	158 ms	19020 KB	Output is correct
13	Correct	131 ms	25116 KB	Output is correct
14	Correct	153 ms	24984 KB	Output is correct
15	Correct	179 ms	23344 KB	Output is correct
16	Correct	128 ms	24884 KB	Output is correct
17	Correct	144 ms	24796 KB	Output is correct
18	Correct	166 ms	22444 KB	Output is correct
19	Correct	108 ms	25296 KB	Output is correct
20	Correct	143 ms	25188 KB	Output is correct
21	Correct	130 ms	25112 KB	Output is correct
22	Correct	177 ms	23376 KB	Output is correct
23	Correct	155 ms	25024 KB	Output is correct
24	Correct	166 ms	19236 KB	Output is correct
25	Correct	493 ms	33792 KB	Output is correct
26	Correct	2139 ms	77632 KB	Output is correct
27	Correct	3345 ms	110912 KB	Output is correct
28	Correct	3376 ms	110568 KB	Output is correct
29	Correct	2077 ms	77308 KB	Output is correct
30	Correct	468 ms	32968 KB	Output is correct
31	Correct	2130 ms	77500 KB	Output is correct
32	Correct	2112 ms	77640 KB	Output is correct
33	Correct	2140 ms	77688 KB	Output is correct
34	Correct	2121 ms	77680 KB	Output is correct
35	Correct	2138 ms	77396 KB	Output is correct
36	Correct	2177 ms	77468 KB	Output is correct
37	Correct	471 ms	33084 KB	Output is correct
38	Correct	3164 ms	76700 KB	Output is correct
39	Execution timed out	5080 ms	80456 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-