Submission #669941

#	Time	Username	Problem	Language	Result	Execution time	Memory
669941		rainboy	청소 (JOI20_sweeping)	C11	1 / 100	18088 ms	53516 KiB

sweeping

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

#define N	1500000
#define Q	1000000

int max(int a, int b) { return a > b ? a : b; }

int tt[Q], ll[Q], rr[Q], xx_[Q], yy_[Q], zz[Q];
int n, q, s;

void solve_(int *hh, int q, int l, int r) {
	int g, h;

	for (h = l; h < r; h++)
		if (tt[h] == 2) {
			for (g = 0; g < q; g++)
				if (yy_[hh[g]] <= zz[h])
					xx_[hh[g]] = max(xx_[hh[g]], s - zz[h]);
		} else if (tt[h] == 3) {
			for (g = 0; g < q; g++)
				if (xx_[hh[g]] <= zz[h])
					yy_[hh[g]] = max(yy_[hh[g]], s - zz[h]);
		}
}

void solve(int *hh, int q, int l, int r) {
	int m, h1, h2, h3, tmp;

	h1 = 0, h2 = 0, h3 = q;
	while (h2 < h3)
		if (ll[hh[h2]] <= l && r <= rr[hh[h2]])
			h2++;
		else if (ll[hh[h2]] < r && l < rr[hh[h2]]) {
			tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
			h1++, h2++;
		} else {
			h3--;
			tmp = hh[h2], hh[h2] = hh[h3], hh[h3] = tmp;
		}
	solve_(hh + h1, h2 - h1, l, r);
	if (r - l > 1) {
		m = (l + r) / 2;
		solve(hh, h1, l, m), solve(hh, h1, m, r);
	}
}

int main() {
	static int xx[N], yy[N], pp[N], hh[Q];
	int m, h, i;

	scanf("%d%d%d", &s, &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	memset(pp, -1, n * sizeof *pp);
	for (h = 0; h < q; h++) {
		scanf("%d", &tt[h]);
		if (tt[h] == 1) {
			scanf("%d", &i), i--;
			ll[h] = pp[i] + 1, rr[h] = h, xx_[h] = xx[i], yy_[h] = yy[i];
		} else if (tt[h] == 2 || tt[h] == 3)
			scanf("%d", &zz[h]);
		else
			scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
	}
	m = 0;
	for (h = 0; h < q; h++)
		if (tt[h] == 1)
			hh[m++] = h;
	solve(hh, m, 0, q);
	for (h = 0; h < q; h++)
		if (tt[h] == 1)
			printf("%d %d\n", xx_[h], yy_[h]);
	return 0;
}

Compilation message (stderr)

sweeping.c: In function 'main':
sweeping.c:52:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d%d", &s, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~
sweeping.c:59:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
sweeping.c:62:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |    scanf("%d", &zz[h]);
      |    ^~~~~~~~~~~~~~~~~~~
sweeping.c:64:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |    scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25