Submission #829489

#	Time	Username	Problem	Language	Result	Execution time	Memory
829489		rainboy	Curtains (NOI23_curtains)	C11	44 / 100	196 ms	13684 KiB

curtains

#include <stdio.h>

#define N	500000
#define SMALL	2000
#define M	500000

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

int main() {
	static int ll[N], qu[N];
	int n, m, q, cnt, l, r;

	scanf("%d%d%d", &n, &m, &q);
	if (n <= SMALL) {
		static char has[SMALL][SMALL], can[SMALL][SMALL];

		while (m--) {
			scanf("%d%d", &l, &r), l--, r--;
			has[l][r] = 1;
		}
		for (r = 0; r < n; r++)
			ll[r] = r + 1;
		for (l = n - 1; l >= 0; l--) {
			for (r = l; r < n; r++)
				if (has[l][r])
					ll[r] = l;
			cnt = 0;
			for (r = l; r < n; r++) {
				qu[cnt++] = r;
				while (cnt && qu[cnt - 1] >= ll[r])
					cnt--;
				can[l][r] = cnt == 0;
			}
		}
		while (q--) {
			scanf("%d%d", &l, &r), l--, r--;
			printf(can[l][r] ? "YES\n" : "NO\n");
		}
	} else {
		static char can[N];

		for (r = 0; r < n; r++)
			ll[r] = r + 1;
		while (m--) {
			scanf("%d%d", &l, &r), l--, r--;
			ll[r] = min(ll[r], l);
		}
		cnt = 0;
		for (r = 0; r < n; r++) {
			qu[cnt++] = r;
			while (cnt && qu[cnt - 1] >= ll[r])
				cnt--;
			can[r] = cnt == 0;
		}
		while (q--) {
			scanf("%d%d", &l, &r), l--, r--;
			printf(can[r] ? "YES\n" : "NO\n");
		}
	}
	return 0;
}

Compilation message (stderr)

curtains.c: In function 'main':
curtains.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:18:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~
curtains.c:36:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~
curtains.c:45:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~
curtains.c:56:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~

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