oj.uz

Submission #768201

# Submission time Handle Problem Language Result Execution time Memory
768201 2023-06-27T16:51:25 Z rainboy Simple game (IZhO17_game) C
100 / 100
 385 ms 6216 KB 
#include <stdio.h>

#define N	100000
#define Q	100000
#define N_	(N + Q + 1)

unsigned int Z = 12345;

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

int zz[N_], ll[N_], rr[N_], aa[N_], xx[N_], ss[N_], u_, l_, r_;

int node(int a, int x) {
	static int _ = 1;

	zz[_] = rand_();
	aa[_] = a, ss[_] = xx[_] = x;
	return _++;
}

void pul(int u) {
	ss[u] = ss[ll[u]] + xx[u] + ss[rr[u]];
}

void split(int u, int a) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (aa[u] < a) {
		split(rr[u], a);
		rr[u] = l_, l_ = u;
	} else if (aa[u] > a) {
		split(ll[u], a);
		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;
	}
}

void tr_update(int a, int x) {
	split(u_, a);
	if (u_ == 0)
		u_ = node(a, x);
	else
		ss[u_] = xx[u_] += x;
	u_ = merge(merge(l_, u_), r_);
}

int tr_query(int a) {
	int u = u_, s = 0;

	while (u)
		if (aa[u] <= a)
			s += ss[u] - ss[rr[u]], u = rr[u];
		else
			u = ll[u];
	return s;
}

int main() {
	static int aa[N];
	int n, q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i + 1 < n; i++)
		if (aa[i] < aa[i + 1])
			tr_update(aa[i], 1), tr_update(aa[i + 1], -1);
		else
			tr_update(aa[i + 1], 1), tr_update(aa[i], -1);
	while (q--) {
		int t, a;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &i, &a), i--;
			if (i > 0) {
				if (aa[i] < aa[i - 1])
					tr_update(aa[i], -1), tr_update(aa[i - 1], 1);
				else
					tr_update(aa[i - 1], -1), tr_update(aa[i], 1);
			}
			if (i + 1 < n) {
				if (aa[i] < aa[i + 1])
					tr_update(aa[i], -1), tr_update(aa[i + 1], 1);
				else
					tr_update(aa[i + 1], -1), tr_update(aa[i], 1);
			}
			aa[i] = a;
			if (i > 0) {
				if (aa[i] < aa[i - 1])
					tr_update(aa[i], 1), tr_update(aa[i - 1], -1);
				else
					tr_update(aa[i - 1], 1), tr_update(aa[i], -1);
			}
			if (i + 1 < n) {
				if (aa[i] < aa[i + 1])
					tr_update(aa[i], 1), tr_update(aa[i + 1], -1);
				else
					tr_update(aa[i + 1], 1), tr_update(aa[i], -1);
			}
		} else {
			scanf("%d", &a);
			printf("%d\n", tr_query(a));
		}
	}
	return 0;
}

Compilation message

game.c: In function 'main':
game.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
game.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
game.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
game.c:96:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |    scanf("%d%d", &i, &a), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~
game.c:123:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |    scanf("%d", &a);
      |    ^~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 40 ms 1648 KB Output is correct
9 Correct 158 ms 5148 KB Output is correct
10 Correct 159 ms 5072 KB Output is correct
11 Correct 30 ms 1476 KB Output is correct
12 Correct 119 ms 3276 KB Output is correct
13 Correct 33 ms 2732 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 304 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 312 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 40 ms 1648 KB Output is correct
9 Correct 158 ms 5148 KB Output is correct
10 Correct 159 ms 5072 KB Output is correct
11 Correct 30 ms 1476 KB Output is correct
12 Correct 119 ms 3276 KB Output is correct
13 Correct 33 ms 2732 KB Output is correct
14 Correct 385 ms 6132 KB Output is correct
15 Correct 367 ms 6144 KB Output is correct
16 Correct 378 ms 6216 KB Output is correct
17 Correct 380 ms 6164 KB Output is correct
18 Correct 371 ms 6092 KB Output is correct