Submission #1111197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111197		sleepntsheep	Curtains (NOI23_curtains)	C11	100 / 100	504 ms	76820 KiB

curtains

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

#define N 500005

int n, m, q, *eh[N], eo[N], *eh_[N], eo_[N], ii[N], ii_[N], ans[N], I[N], qr[N], ql[N];

void pus(int **eh, int *eo, int i, int j) {
	int o = eo[i]++;
	if (!o) eh[i] = (int*)malloc(2 * sizeof **eh);
	else if (!(o & (o - 1))) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
	eh[i][o] = j;
}

int cmpr(const void *i, const void *j) {
	return *(const int*)i - *(const int*)j;
}

void dnc(int x, int y, int *a, int q) {
	if (x > y) 
		return;

	int *al = 0, *ar = 0, ao = 0, ao_ = 0, m = (x + y) / 2;
	for (int i = 0; i < q; ++i) 
		if (qr[a[i]] < m) 
			pus(&al, &ao, 0, a[i]);

	dnc(x, m - 1, al, ao);
	free(al);

	static int closeL[N], closeR[N], stk[N], sz;
	sz = 0;
	
	for (int i = m; i >= x; --i) {
		while (eh[i][ii[i] + 1] < m) ++ii[i];
		int opt = eh[i][ii[i] + 1], rr = eh[i][ii[i]];
		if (rr < m)
			for (; sz && stk[sz] <= rr + 1; --sz)
				if (opt > closeL[stk[sz]])
					opt = closeL[stk[sz]];
		stk[++sz] = i;
		closeL[i] = opt;
	}
	
	sz = 0;
	for (int i = m; i <= y; ++i) {
		while (eh_[i][ii_[i] + 1] <= m) ++ii_[i];
		int opt = eh_[i][ii_[i]], ll = eh_[i][ii_[i] + 1];
		if (ll > m)
			for (; sz && stk[sz] >= ll - 1; --sz)
				if (opt < closeR[stk[sz]])
					opt = closeR[stk[sz]];
		stk[++sz] = i;
		closeR[i] = opt;
	}

	for (int i = 0; i < q; ++i) {
		int l = ql[a[i]], r = qr[a[i]];
		if (l <= m && m <= r)
			ans[a[i]] = closeL[l] <= r && closeR[r] >= l;
		else if (l > m)
			pus(&ar, &ao_, 0, a[i]);
	}

	dnc(m + 1, y, ar, ao_);
	free(ar);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = m, l, r; i--;)
		scanf("%d%d", &l, &r),
		pus(eh, eo, l, r),
		pus(eh_, eo_, r, l);
	
	for (int i = 1; i <= n; ++i)
		pus(eh, eo, i, i - 1),
		pus(eh, eo, i, N + 1),
		pus(eh_, eo_, i, i + 1),
		pus(eh_, eo_, i, 0),
		qsort(eh[i], eo[i], sizeof **eh, cmpr),
		qsort(eh_[i], eo_[i], sizeof **eh_, cmpr);

	for (int i = 0; i < q; ++i)
		scanf("%d%d", ql + i, qr + i), I[i] = i;

	dnc(1, n, I, q);
	
	for (int i = 0; i < q; ++i)
		puts(ans[i]? "YES": "NO");
}

Compilation message (stderr)

curtains.c: In function 'main':
curtains.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d", &l, &r),
      |   ^~~~~~~~~~~~~~~~~~~~~
curtains.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", ql + i, qr + i), I[i] = i;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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