Submission #829665

#	Time	Username	Problem	Language	Result	Execution time	Memory
829665		rainboy	Curtains (NOI23_curtains)	C11	100 / 100	406 ms	31664 KiB

curtains

#include <stdio.h>

#define N	500000
#define K	500000
#define Q	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N)) */
#define INF	0x3f3f3f3f

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

int st[N_ * 2], n_, mode;

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		st[n_ + i] = i < n ? aa[i] : (mode == 0 ? INF : -1);
	for (i = n_ - 1; i > 0; i--)
		st[i] = mode == 0 ? min(st[i << 1 | 0], st[i << 1 | 1]) : max(st[i << 1 | 0], st[i << 1 | 1]);
}

int query(int l, int r) {
	int x = mode == 0 ? INF : -1;

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

int ll[K], rr[K];
int ll_[Q], rr_[Q]; char yes[Q];

void solve(int *gg, int k, int *hh, int q, int l, int r) {
	static int ii[N], jj[N], qu[N];
	int m, cnt, g, g_, g1, g2, g3, h, h_, h1, h2, h3, i, j, tmp;

	if (l == r) {
		if (k == 0)
			for (h = 0; h < q; h++)
				yes[hh[h]] = 0;
		return;
	}
	m = (l + r) / 2;
	g1 = g2 = 0, g3 = k;
	while (g2 < g3)
		if (ll[gg[g2]] <= m && m < rr[gg[g2]])
			g2++;
		else if (rr[gg[g2]] <= m) {
			tmp = gg[g1], gg[g1] = gg[g2], gg[g2] = tmp;
			g1++, g2++;
		} else {
			g3--;
			tmp = gg[g2], gg[g2] = gg[g3], gg[g3] = tmp;
		}
	h1 = h2 = 0, h3 = q;
	while (h2 < h3)
		if (ll_[hh[h2]] <= m && m < rr_[hh[h2]])
			h2++;
		else if (rr_[hh[h2]] <= m) {
			tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
			h1++, h2++;
		} else {
			h3--;
			tmp = hh[h2], hh[h2] = hh[h3], hh[h3] = tmp;
		}
	for (i = l; i <= m; i++)
		jj[i] = i - 1;
	for (g = 0; g < g1; g++) {
		g_ = gg[g];
		jj[ll[g_]] = max(jj[ll[g_]], rr[g_]);
	}
	cnt = 0;
	for (i = m; i >= l; i--) {
		qu[cnt++] = i;
		while (cnt && qu[cnt - 1] <= jj[i])
			cnt--;
		ii[i] = cnt == 0 ? -1 : qu[cnt - 1];
	}
	for (i = l; i <= m; i++)
		jj[i] = r + 1;
	for (g = g1; g < g2; g++) {
		g_ = gg[g];
		jj[ll[g_]] = min(jj[ll[g_]], rr[g_]);
	}
	mode = 0, build(jj + l, m - l + 1);
	for (h = h1; h < h2; h++) {
		h_ = hh[h];
		if ((i = ii[ll_[h_]]) != -1 && query(ll_[h_] - l, i - l) > rr_[h_])
			yes[h_] = 0;
	}
	for (j = m + 1; j <= r; j++)
		ii[j] = j + 1;
	for (g = g2; g < k; g++) {
		g_ = gg[g];
		ii[rr[g_]] = min(ii[rr[g_]], ll[g_]);
	}
	cnt = 0;
	for (j = m + 1; j <= r; j++) {
		qu[cnt++] = j;
		while (cnt && qu[cnt - 1] >= ii[j])
			cnt--;
		jj[j] = cnt == 0 ? -1 : qu[cnt - 1];
	}
	for (j = m + 1; j <= r; j++)
		ii[j] = l - 1;
	for (g = g1; g < g2; g++) {
		g_ = gg[g];
		ii[rr[g_]] = max(ii[rr[g_]], ll[g_]);
	}
	mode = 1, build(ii + m + 1, r - m);
	for (h = h1; h < h2; h++) {
		h_ = hh[h];
		if ((j = jj[rr_[h_]]) != -1 && query(j - (m + 1), rr_[h_] - (m + 1)) < ll_[h_])
			yes[h_] = 0;
	}
	solve(gg, g1, hh, h1, l, m), solve(gg + g2, k - g2, hh + h2, q - h2, m + 1, r);
}

int main() {
	static int gg[K], hh[Q];
	int n, k, q, g, h;

	scanf("%d%d%d", &n, &k, &q);
	for (g = 0; g < k; g++) {
		scanf("%d%d", &ll[g], &rr[g]), ll[g]--, rr[g]--;
		gg[g] = g;
	}
	for (h = 0; h < q; h++) {
		scanf("%d%d", &ll_[h], &rr_[h]), ll_[h]--, rr_[h]--;
		hh[h] = h;
	}
	for (h = 0; h < q; h++)
		yes[h] = 1;
	solve(gg, k, hh, q, 0, n - 1);
	for (h = 0; h < q; h++)
		printf(yes[h] ? "YES\n" : "NO\n");
	return 0;
}

Compilation message (stderr)

curtains.c: In function 'main':
curtains.c:131:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d%d", &ll[g], &rr[g]), ll[g]--, rr[g]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:137:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%d%d", &ll_[h], &rr_[h]), ll_[h]--, rr_[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20