제출 #683922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683922		rainboy	Long Mansion (JOI17_long_mansion)	C11	100 / 100	460 ms	92592 KiB

long_mansion

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

#define N	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N + 1))) */

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

int *ea[N], eo[N], *ei[N], *ej[N], eo_[N];

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int st[N_ * 2], n_;

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

int floor_(int r) {
	int l;

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

int ceil_(int l) {
	int r;

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

int main() {
	static int aa[N], pp[N], ll[N], rr[N], qu[N], ll_[N], rr_[N];
	int n, q, i, j, o, cnt;

	scanf("%d", &n);
	for (i = 0; i + 1 < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	for (i = 0; i < n; i++) {
		scanf("%d", &eo[i]);
		ea[i] = (int *) malloc(eo[i] * sizeof *ea[i]);
		for (o = eo[i]; o--; )
			scanf("%d", &ea[i][o]), ea[i][o]--;
	}
	for (i = 0; i < n; i++)
		pp[i] = -1;
	for (i = 0; i < n; i++) {
		for (o = eo[i]; o--; ) {
			int a = ea[i][o];

			pp[a] = i;
		}
		ll[i] = i + 1 == n ? -1 : pp[aa[i]];
	}
	for (i = 0; i < n; i++)
		pp[i] = n;
	for (i = n - 1; i >= 0; i--) {
		for (o = eo[i]; o--; ) {
			int a = ea[i][o];

			pp[a] = i;
		}
		rr[i] = i == 0 ? n : pp[aa[i - 1]];
	}
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	for (j = 0; j < n; j++)
		ei[j] = (int *) malloc(2 * sizeof *ei[j]), eo_[j] = 0;
	for (i = 0; i < n; i++)
		if (rr[i] < n)
			append(ei, eo_, rr[i], i);
	memset(st, 0, n_ * 2 * sizeof *st);
	cnt = 0;
	for (j = 0; j < n; j++) {
		update(j, 1);
		for (o = eo_[j]; o--; ) {
			i = ei[j][o];
			update(i, -1);
		}
		qu[cnt++] = j;
		i = ceil_(ll[j] + 1);
		if (i != -1)
			while (cnt && qu[cnt - 1] >= i)
				rr_[qu[--cnt]] = j;
	}
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo_[i] = 0;
	for (j = 0; j < n; j++)
		if (ll[j] >= 0)
			append(ej, eo_, ll[j], j);
	memset(st, 0, n_ * 2 * sizeof *st);
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		update(i, 1);
		for (o = eo_[i]; o--; ) {
			j = ej[i][o];
			update(j, -1);
		}
		qu[cnt++] = i;
		j = floor_(rr[i] - 1);
		if (j != -1)
			while (cnt && qu[cnt - 1] <= j)
				ll_[qu[--cnt]] = i;
	}
	scanf("%d", &q);
	while (q--) {
		int i, j;

		scanf("%d%d", &i, &j), i--, j--;
		printf(ll_[i] <= j && j <= rr_[i] ? "YES\n" : "NO\n");
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.c: In function 'append':
long_mansion.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
long_mansion.c: In function 'main':
long_mansion.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
long_mansion.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
long_mansion.c:66:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d", &eo[i]);
      |   ^~~~~~~~~~~~~~~~~~~
long_mansion.c:69:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf("%d", &ea[i][o]), ea[i][o]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~
long_mansion.c:132:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
long_mansion.c:136:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75