Submission #871105

#	Time	Username	Problem	Language	Result	Execution time	Memory
871105		rainboy	Santa Claus (RMI19_santa)	C11	90 / 100	211 ms	13392 KiB

santa

#include <stdio.h>
#include <string.h>

#define N	96068
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */

int max(int a, int b) { return a > b ? a : b; }

int n_;

int ss[N_ * 2], pp[N_ * 2];

void pul(int i) {
	int l = i << 1, r = l | 1;

	ss[i] = ss[l] + ss[r];
	pp[i] = max(pp[l], ss[l] + pp[r]);
}

void update(int i, int x) {
	i += n_;
	pp[i] = max(ss[i] += x, 0);
	while (i > 1)
		pul(i >>= 1);
}

int ss_[N_ * 2];

void update_(int i, int x) {
	for (i += n_; i > 0; i >>= 1)
		ss_[i] += x;
}

int query_(int l) {
	int r = n_ - 1;

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

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int xx[N], aa[N], tt[N];
		int n, h, i, i_, j, l, a;

		scanf("%d", &n);
		for (i = 0; i < n; i++)
			scanf("%d", &xx[i]);
		i_ = -1;
		for (i = 0; i < n; i++) {
			scanf("%d", &tt[i]);
			if (tt[i] == 0)
				i_ = i;
		}
		for (i = 0; i < n; i++)
			scanf("%d", &aa[i]);
		n_ = 1;
		while (n_ < n + 1)
			n_ <<= 1;
		memset(ss, 0, n_ * 2 * sizeof *ss), memset(pp, 0, n_ * 2 * sizeof *pp);
		memset(ss_, 0, n_ * 2 * sizeof *ss_);
		for (i = 0, l = 0; i < n; i = j) {
			j = i + 1;
			while (j < n && xx[j] == xx[i])
				j++;
			for (h = i; h < j; h++)
				update(aa[h], tt[h] == 0 ? 1 : -1);
			if (j > i_)
				while (l < j && pp[1] == 0) {
					if (tt[l] == 0)
						update_(aa[l], 1);
					else {
						update(aa[l], 1);
						if ((a = query_(aa[l])) != -1)
							update(a, -1), update_(a, -1);
					}
					l++;
				}
			for (h = i; h < j; h++)
				printf("%d ", l == 0 ? -1 : xx[j - 1] * 2 - xx[l - 1]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

santa.c: In function 'main':
santa.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
santa.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
santa.c:59:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &xx[i]);
      |    ^~~~~~~~~~~~~~~~~~~
santa.c:62:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |    scanf("%d", &tt[i]);
      |    ^~~~~~~~~~~~~~~~~~~
santa.c:67:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |    scanf("%d", &aa[i]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100