Submission #693307

#	Time	Username	Problem	Language	Result	Execution time	Memory
693307		rainboy	Matryoshka (JOI16_matryoshka)	C11	100 / 100	284 ms	16036 KiB

matryoshka

#include <stdio.h>

#define N	200000
#define Q	200000
#define M	(N + Q)

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 *gg, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, g = gg[l + rand_() % (r - l)], tmp;

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

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

int ft[M];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int xx[M], yy[M], gg[M], ans[Q];
	int n, q, m, g, h, i, y;

	scanf("%d%d", &n, &q), m = n + q;
	for (g = 0; g < m; g++) {
		scanf("%d%d", &xx[g], &yy[g]);
		xx[g] = -xx[g];
	}
	for (g = 0; g < m; g++)
		gg[g] = g;
	uu = yy, vv = yy, sort(gg, 0, m);
	for (g = 0, y = 0; g < m; g++)
		yy[gg[g]] = g + 1 == m || yy[gg[g + 1]] != yy[gg[g]] ? y++ : y;
	uu = xx, vv = yy, sort(gg, 0, m);
	for (g = 0; g < m; g++)
		if (gg[g] < n) {
			i = gg[g];
			update(yy[i], m, query(yy[i]) + 1);
		} else {
			h = gg[g] - n;
			ans[h] = query(yy[n + h]);
		}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

matryoshka.c: In function 'main':
matryoshka.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d", &n, &q), m = n + q;
      |  ^~~~~~~~~~~~~~~~~~~~~
matryoshka.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", &xx[g], &yy[g]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49