Submission #728024

#	Time	Username	Problem	Language	Result	Execution time	Memory
728024		rainboy	trapezoid (balkan11_trapezoid)	C11	100 / 100	101 ms	7612 KiB

trapezoid

#include <stdio.h>

#define N	100000
#define MD	30013

unsigned int X = 12345;

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

int xx[N * 2], yy[N * 2];

int *zz;

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)
			if (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[i_]) {
				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 ftu[N * 2], ftv[N * 2];

void update(int i, int n, int u, int v) {
	while (i < n) {
		if (ftu[i] < u)
			ftu[i] = u, ftv[i] = 0;
		if (ftu[i] == u)
			ftv[i] = (ftv[i] + v) % MD;
		i |= i + 1;
	}
}

void query(int i, int *u, int *v) {
	*u = 0, *v = 1;
	while (i >= 0) {
		if (*u < ftu[i])
			*u = ftu[i], *v = 0;
		if (*u == ftu[i])
			*v = (*v + ftv[i]) % MD;
		i &= i + 1, i--;
	}
}

int main() {
	static int ii[N * 2], dp[N], dq[N];
	int n, h, i, i_, u, v;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d%d%d", &xx[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 0], &yy[i << 1 | 1]);
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	zz = yy, sort(ii, 0, n * 2);
	for (i = 0; i < n * 2; i++)
		yy[ii[i]] = i;
	zz = xx, sort(ii, 0, n * 2);
	for (h = 0; h < n * 2; h++) {
		i_ = ii[h], i = i_ >> 1;
		if ((i_ & 1) == 0)
			query(yy[i_], &dp[i], &dq[i]), dp[i]++;
		else
			update(yy[i_], n * 2, dp[i], dq[i]);
	}
	query(n * 2 - 1, &u, &v);
	printf("%d %d\n", u, v);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100