Submission #788100

#	Time	Username	Problem	Language	Result	Execution time	Memory
788100		rainboy	Towers (NOI22_towers)	C11	100 / 100	565 ms	50100 KiB

Main

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

#define N	1000000
#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; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *uu, *vv;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = uu[ii[j]] != uu[i_] ? uu[ii[j]] - uu[i_] : vv[ii[j]] - vv[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int xx[N], yy[N], iix[N], iiy[N], hhx[N], hhy[N], hxl[N], hxr[N], hyl[N], hyr[N];

void add(int i) {
	int x, y, hx, hy, tmp;

	y = yy[i], hy = hhy[i];
	if (hyl[y] >= hyr[y])
		hyl[y] = min(hyl[y], hy), hyr[y] = max(hyr[y], hy);
	else {
		if (hyl[y] > hy)
			tmp = hy, hy = hyl[y], hyl[y] = tmp;
		else if (hyr[y] < hy)
			tmp = hy, hy = hyr[y], hyr[y] = tmp;
		i = iiy[hy];
		x = xx[i], hx = hhx[i];
		if (hx == hxl[x])
			hx = ++hxl[x];
		else if (hx == hxr[x])
			hx = --hxr[x];
		if (hxl[x] < hxr[x])
			add(iix[hx]);
	}
}

int main() {
	static char cc[N + 1];
	int n, nx, ny, h, i, x;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		iix[i] = i;
	uu = xx, vv = yy, sort(iix, 0, n);
	nx = 0;
	for (h = 0; h < n; h++) {
		i = iix[h];
		xx[i] = h + 1 == n || xx[iix[h + 1]] != xx[i] ? nx++ : nx;
		hhx[i] = h;
	}
	for (i = 0; i < n; i++)
		iiy[i] = i;
	uu = yy, vv = xx, sort(iiy, 0, n);
	ny = 0;
	for (h = 0; h < n; h++) {
		i = iiy[h];
		yy[i] = h + 1 == n || yy[iiy[h + 1]] != yy[i] ? ny++ : ny;
		hhy[i] = h;
	}
	memset(hxl, 0x3f, nx * sizeof *hxl), memset(hxr, -1, nx * sizeof *hxr);
	memset(hyl, 0x3f, ny * sizeof *hyl), memset(hyr, -1, ny * sizeof *hyr);
	for (h = 0; h < n; h++) {
		i = iix[h], x = xx[i];
		hxl[x] = min(hxl[x], hhx[i]), hxr[x] = max(hxr[x], hhx[i]);
	}
	for (x = 0; x < nx; x++) {
		add(iix[hxl[x]]);
		if (hxl[x] < hxr[x])
			add(iix[hxr[x]]);
	}
	for (x = 0; x < nx; x++)
		if (hxl[x] <= hxr[x])
			cc[iix[hxl[x]]] = cc[iix[hxr[x]]] = 1;
	for (i = 0; i < n; i++)
		cc[i] += '0';
	printf("%s\n", cc);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:68:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 31 / 31
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19