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

santa

#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]);
      |    ^~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	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