Submission #768170

#	Time	Username	Problem	Language	Result	Execution time	Memory
768170		rainboy	Money (IZhO17_money)	C11	45 / 100	1584 ms	30340 KiB

money

#include <stdio.h>

#define N	1000000

unsigned int Z = 12345;

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

int zz[N + 1], ll[N + 1], rr[N + 1], aa[N + 1], kk[N + 1], u_, l_, r_;

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

	zz[_] = rand_();
	aa[_] = a, kk[_] = k;
	return _++;
}

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;
	}
}

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);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

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

int tr_floor(int a) {
	int u = u_, a_ = -1;

	while (u)
		if (aa[u] <= a)
			a_ = aa[u], u = rr[u];
		else
			u = ll[u];
	return a_;
}

int main() {
	static int aa[N];
	int n, i, j, k, a;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		tr_update(aa[i], 1);
	}
	k = 0;
	for (j = n - 1; j >= 0; j = i) {
		i = j - 1;
		while (i >= 0 && aa[i] == aa[j])
			i--;
		tr_update(aa[j], -(j - i));
		a = aa[j] - 1;
		while (i >= 0 && aa[i] == tr_floor(a))
			tr_update(aa[i], -1), a = aa[i], i--;
		k++;
	}
	printf("%d\n", k);
	return 0;
}

Compilation message (stderr)

money.c: In function 'main':
money.c:76:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
money.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 55