Submission #76938682

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define N_MAX 212345
#define M_MAX 212345
#define Q_MAX 212345
#define INF 1010101010
#define KI_MAX (1 << 18) /* 262144 */
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int N, M;
int L[M_MAX], R[M_MAX];
int Q;
int S[Q_MAX], T[Q_MAX];
int start_cnt[N_MAX], *start[N_MAX];
int end_cnt[N_MAX], *end[N_MAX];
int ki[KI_MAX * 2 - 1];
void ki_set(int pos, int value) {
  pos += KI_MAX - 1;
  if (ki[pos] > value) ki[pos] = value;
  do {
    pos = (pos - 1) / 2;
    ki[pos] = ki[pos * 2 + 1] <= ki[pos * 2 + 2] ? ki[pos * 2 + 1] : ki[pos * 2 + 2];
  } while (pos > 0);
}
int ki_get_i(int pos, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    return ki[pos];
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    return INF;
  } else {
    int sm = ss + (se - ss) / 2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define N_MAX 212345
#define M_MAX 212345
#define Q_MAX 212345

#define INF 1010101010
#define KI_MAX (1 << 18) /* 262144 */

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int N, M;
int L[M_MAX], R[M_MAX];
int Q;
int S[Q_MAX], T[Q_MAX];

int start_cnt[N_MAX], *start[N_MAX];
int end_cnt[N_MAX], *end[N_MAX];

int ki[KI_MAX * 2 - 1];

void ki_set(int pos, int value) {
	pos += KI_MAX - 1;
	if (ki[pos] > value) ki[pos] = value;
	do {
		pos = (pos - 1) / 2;
		ki[pos] = ki[pos * 2 + 1] <= ki[pos * 2 + 2] ? ki[pos * 2 + 1] : ki[pos * 2 + 2];
	} while (pos > 0);
}

int ki_get_i(int pos, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[pos];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return INF;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_get_i(pos * 2 + 1, ss, sm, qs, qe);
		int r = ki_get_i(pos * 2 + 2, sm, se, qs, qe);
		return l <= r ? l : r;
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d%d", &L[i], &R[i]) != 2) return 1;
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &S[i], &T[i]) != 2) return 1;
	}

	for (i = 0; i < (int)(sizeof(ki) / sizeof(*ki)); i++) ki[i] = INF;

	for (i = 0; i < M; i++) {
		start[L[i]] = realloc(start[L[i]], sizeof(**start) * (start_cnt[L[i]] + 1));
		if (start[L[i]] == NULL) return 2;
		start[L[i]][start_cnt[L[i]]++] = R[i];

		end[R[i]] = realloc(end[R[i]], sizeof(**end) * (end_cnt[R[i]] + 1));
		if (end[R[i]] == NULL) return 2;
		end[R[i]][end_cnt[R[i]]++] = L[i];

		ki_set(L[i], R[i]);
	}

	for (i = 1; i <= N; i++) {
		if (start_cnt[i] > 0) qsort(start[i], start_cnt[i], sizeof(**start), cmp);
		if (end_cnt[i] > 0) qsort(end[i], end_cnt[i], sizeof(**end), cmp);
	}

	for (i = 0; i < Q; i++) {
		int s_le = -1, s_g = start_cnt[S[i]];
		while (s_le + 1 < s_g) {
			int m = s_le + (s_g - s_le) / 2;
			if (start[S[i]][m] <= T[i]) s_le = m; else s_g = m;
		}
		if (s_le >= 0) {
			if (start[S[i]][s_le] == T[i]) {
				/* S[i] から T[i] をちょうど覆う布がある */
				if (s_le > 0) {
					/* それとは別に S[i] から T[i] またはそれより前までのみを覆う布がある */
					puts("Yes");
				} else if (ki_get(S[i] + 1, T[i] + 1) <= T[i]) {
					/* S[i] の次以降から始まって、T[i] またはそれより前までのみを覆う布がある */
					puts("Yes");
				} else {
					/* 都合のいいもう1枚の布がない */
					puts("No");
				}
			} else {
				/* S[i] から T[i] より前までを覆う布がある */
				int e_l = -1, e_ge = end_cnt[T[i]];
				while (e_l + 1 < e_ge) {
					int m = e_l + (e_ge - e_l) / 2;
					if (S[i] <= end[T[i]][m]) e_ge = m; else e_l = m;
				}
				if (e_ge < end_cnt[T[i]] && end[T[i]][e_ge] <= start[S[i]][s_le] + 1) {
					/* S[i] からの布と組み合わせていい感じになる布がある */
					puts("Yes");
				} else {
					/* 覆う範囲が足りないか、そもそも S[i] を超えない範囲を覆う布がない */
					puts("No");
				}
			}
		} else {
			/* S[i] から始まって、T[i] またはそれより前までのみを覆う布は無い */
			puts("No");
		}
	}

	return 0;
}

/*

A. 2枚で協力する

・S_q で始まって T_q を超えない中で一番長いやつ
・T_q で終わって S_q を超えない中で一番長いやつ
でいける ⇔ Yes

B. 1枚でいけるので、1枚捨てる

・S_q で始まって T_q で終わるやつがある
・S_q またはその後ろで始まって T_q またはその前で終わるやつがある
⇔ Yes

☆ 同じ布の二重カウントに注意 (特に S_q で始まって T_q で終わるやつ)
S_q で始まって T_q で終わるやつがあったら
その1個前 (昇順) を見る
→ それが T_q またはその前で終われば Yes (というか、昇順なのであれば必ずこの条件を満たす)
   無かったら → (S_q, T_q] で始まり、T_q またはその前で終わるやつがある ⇔ Yes

「始まる位置」に「終わる位置」を書き込んだセグ木で最小値を求める

*/

Submission Info

Judge Result