Submission #871109

# Submission time Handle Problem Language Result Execution time Memory
871109 2023-11-09T23:04:08 Z rainboy Santa Claus (RMI19_santa) C
100 / 100
220 ms 6796 KB
#include <stdio.h>
#include <string.h>

#define N	100000
#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, i, j, k, a;

		scanf("%d", &n);
		for (i = 0; i < n; i++)
			scanf("%d", &xx[i]);
		k = -1;
		for (i = 0; i < n; i++) {
			scanf("%d", &tt[i]);
			if (tt[i] == 0)
				k = 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, j = 0; j < n; j++) {
			update(aa[j], tt[j] == 0 ? 1 : -1);
			if (j >= k)
				while (i <= j && pp[1] == 0) {
					if (tt[i] == 0)
						update_(aa[i], 1);
					else {
						update(aa[i], 1);
						if ((a = query_(aa[i])) != -1)
							update(a, -1), update_(a, -1);
					}
					i++;
				}
			printf("%d ", i == 0 ? -1 : xx[j] * 2 - xx[i - 1]);
		}
		printf("\n");
	}
	return 0;
}

Compilation message

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]);
      |    ^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 13 ms 2636 KB Output is correct
5 Correct 24 ms 2900 KB Output is correct
6 Correct 40 ms 3252 KB Output is correct
7 Correct 72 ms 3772 KB Output is correct
8 Correct 112 ms 4432 KB Output is correct
9 Correct 147 ms 6312 KB Output is correct
10 Correct 220 ms 6796 KB Output is correct