oj.uz

Submission #745287

# Submission time Handle Problem Language Result Execution time Memory
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 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -