Submission #728024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
728024	2023-04-21T19:58:39 Z	rainboy	trapezoid (balkan11_trapezoid)	C	100 / 100	101 ms	7612 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	3 ms	500 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	9 ms	932 KB	Output is correct
10	Correct	16 ms	1676 KB	Output is correct
11	Correct	22 ms	2056 KB	Output is correct
12	Correct	48 ms	3916 KB	Output is correct
13	Correct	57 ms	4588 KB	Output is correct
14	Correct	74 ms	5536 KB	Output is correct
15	Correct	79 ms	5708 KB	Output is correct
16	Correct	80 ms	6100 KB	Output is correct
17	Correct	82 ms	6504 KB	Output is correct
18	Correct	81 ms	6848 KB	Output is correct
19	Correct	99 ms	7268 KB	Output is correct
20	Correct	101 ms	7612 KB	Output is correct