oj.uz

답안 #669941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669941 2022-12-07T16:13:57 Z rainboy 청소 (JOI20_sweeping) C
1 / 100
 18000 ms 53516 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 9 ms 468 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 18017 ms 53516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 18088 ms 51256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 18088 ms 51256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 596 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 9 ms 468 KB Output is correct
7 Execution timed out 18017 ms 53516 KB Time limit exceeded
8 Halted 0 ms 0 KB -