Submission #740610

#	Time	Username	Problem	Language	Result	Execution time	Memory
740610		rainboy	Exercise Deadlines (CCO20_day1problem2)	C11	25 / 25	58 ms	4228 KiB

Main

#include <stdio.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N + 1))) */

int st[N_ * 2], n_;

void build(int n) {
	int i;

	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i] = 1;
	for (i = n_ - 1; i > 0; i--)
		st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}

void update(int i) {
	for (i += n_; i > 0; i >>= 1)
		st[i]--;
}

int query(int l) {
	int r = n_ - 1, x = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1)
			x += st[l++];
	return x;
}

int prev(int r) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st[r]) {
				while (r < n_)
					r = st[r << 1 | 1] ? r << 1 | 1 : r << 1 | 0;
				return r - n_;
			}
			r--;
		}
	return -1;
}

int main() {
	static int dd[N];
	int n, i, d;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &dd[i]), dd[i]--;
	build(n);
	ans = 0;
	for (i = n - 1; i >= 0; i--) {
		if ((d = prev(dd[i])) == -1) {
			printf("-1\n");
			return 0;
		}
		ans += query(d + 1);
		update(d);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8