Submission #768201

#	Time	Username	Problem	Language	Result	Execution time	Memory
768201		rainboy	Simple game (IZhO17_game)	C11	100 / 100	385 ms	6216 KiB

game

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

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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51