oj.uz

Submission #670013

# Submission time Handle Problem Language Result Execution time Memory
670013 2022-12-07T18:36:07 Z rainboy Sweeping (JOI20_sweeping) C
22 / 100
 3257 ms 204172 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	1500000
#define Q	1000000
#define LN	20	/* LN = ceil(log2(Q)) */
#define N_	(Q * (LN + 1) * 2 + 1)
#define INF	0x3f3f3f3f

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

unsigned int X = 12345;

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

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

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)
			if (zz[gg[j]] == zz[g])
				j++;
			else if (zz[gg[j]] < zz[g]) {
				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 *hh_, ll_[N_], rr_[N_], xx1[N_], yy1[N_], xx2[N_], yy2[N_], _;

int node() {
	ll_[_] = rr_[_] = 0;
	return _++;
}

void pul(int t) {
	if (t) {
		int l = ll_[t], r = rr_[t];

		xx1[t] = min(xx1[l], xx1[r]), xx2[t] = max(xx2[l], xx2[r]);
		yy1[t] = min(yy1[l], yy1[r]), yy2[t] = max(yy2[l], yy2[r]);
	}
}

int build(int l, int r) {
	int t = node();

	if (r - l > 1) {
		int m = (l + r) / 2;

		ll_[t] = build(l, m), rr_[t] = build(m, r), pul(t);
	} else
		xx1[t] = xx2[t] = xx_[hh_[l]], yy1[t] = yy2[t] = yy_[hh_[l]];
	return t;
}

void split_x(int t, int x, int *t1, int *t2) {
	if (t == 0)
		*t1 = *t2 = 0;
	else if (xx2[t] <= x)
		*t1 = t, *t2 = 0;
	else if (xx1[t] > x)
		*t1 = 0, *t2 = t;
	else {
		int t1_, l1_, l2_, t2_, r1_, r2_;

		split_x(ll_[t], x, &l1_, &l2_), split_x(rr_[t], x, &r1_, &r2_);
		t1_ = t, t2_ = node();
		ll_[t1_] = l1_, rr_[t1_] = r1_, pul(t1_);
		ll_[t2_] = l2_, rr_[t2_] = r2_, pul(t2_);
		*t1 = t1_, *t2 = t2_;
	}
}

void split_y(int t, int y, int *t1, int *t2) {
	if (t == 0)
		*t1 = *t2 = 0;
	else if (yy2[t] <= y)
		*t1 = t, *t2 = 0;
	else if (yy1[t] > y)
		*t1 = 0, *t2 = t;
	else {
		int t1_, l1_, l2_, t2_, r1_, r2_;

		split_y(ll_[t], y, &l1_, &l2_), split_y(rr_[t], y, &r1_, &r2_);
		t1_ = t, t2_ = node();
		ll_[t1_] = l1_, rr_[t1_] = r1_, pul(t1_);
		ll_[t2_] = l2_, rr_[t2_] = r2_, pul(t2_);
		*t1 = t1_, *t2 = t2_;
	}
}

void print(int t, int l, int r, int x, int y) {
	if (t == 0)
		return;
	if (r - l > 1) {
		int m = (l + r) / 2;

		print(ll_[t], l, m, x, y), print(rr_[t], m, r, x, y);
	} else
		xx_[hh_[l]] = max(xx_[hh_[l]], x), yy_[hh_[l]] = max(yy_[hh_[l]], y);
}

int gg[Q], ll1[Q], rr1[Q];

void dfs(int q, int g, int t, int x, int y) {
	int g_, t1, t2;

	if (g == -1)
		print(t, 0, q, x, y);
	else {
		g_ = gg[g];
		if (tt[g_] == 2) {
			split_y(t, s - zz[g_], &t1, &t2);
			dfs(q, ll1[g], t2, x, y), dfs(q, rr1[g], t1, max(x, zz[g_]), y);
		} else if (tt[g_] == 3) {
			split_x(t, zz[g_], &t1, &t2);
			dfs(q, ll1[g], t1, x, max(y, s - zz[g_])), dfs(q, rr1[g], t2, x, y);
		}
	}
}

void solve_(int *hh, int q, int l, int r) {
	static int qu[Q], pp[Q], qq[Q];
	int m, g, g_, cnt;

	m = 0;
	for (g = l; g < r; g++)
		if (tt[g] == 2 || tt[g] == 3)
				gg[m++] = g;
	if (m == 0 || q == 0)
		return;
	sort(gg, 0, m);
	cnt = 0;
	for (g = 0; g < m; g++) {
		while (cnt && gg[qu[cnt - 1]] > gg[g])
			cnt--;
		pp[g] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = g;
	}
	cnt = 0;
	for (g = m - 1; g >= 0; g--) {
		while (cnt && gg[qu[cnt - 1]] > gg[g])
			cnt--;
		qq[g] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = g;
	}
	memset(ll1, -1, m * sizeof *ll1), memset(rr1, -1, m * sizeof *rr1);
	g_ = -1;
	for (g = 0; g < m; g++)
		if (pp[g] == -1 && qq[g] == -1)
			g_ = g;
		else if (qq[g] == -1 || pp[g] != -1 && gg[pp[g]] > gg[qq[g]])
			rr1[pp[g]] = g;
		else
			ll1[qq[g]] = g;
	hh_ = hh;
	_ = 1, xx1[0] = INF, xx2[0] = -1, yy1[0] = INF, yy2[0] = -1;
	dfs(q, g_, build(0, q), 0, 0);
}

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", &yy[i], &xx[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]);
			tt[h] ^= 1;
			if (tt[h] == 2)
				zz[h] = s - zz[h];
		} else
			scanf("%d%d", &yy[n], &xx[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", yy_[h], xx_[h]);
	return 0;
}

Compilation message

sweeping.c: In function 'solve_':
sweeping.c:166:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  166 |   else if (qq[g] == -1 || pp[g] != -1 && gg[pp[g]] > gg[qq[g]])
      |                           ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c: In function 'main':
sweeping.c:200:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |  scanf("%d%d%d", &s, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:202:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |   scanf("%d%d", &yy[i], &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:205:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~
sweeping.c:207:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
sweeping.c:210:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |    scanf("%d", &zz[h]);
      |    ^~~~~~~~~~~~~~~~~~~
sweeping.c:215:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |    scanf("%d%d", &yy[n], &xx[n]), pp[n] = h, n++;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1080 KB Output is correct
2 Correct 7 ms 696 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3257 ms 124076 KB Output is correct
2 Correct 3166 ms 124360 KB Output is correct
3 Correct 3131 ms 124260 KB Output is correct
4 Correct 1695 ms 113836 KB Output is correct
5 Correct 1487 ms 80700 KB Output is correct
6 Correct 1480 ms 204172 KB Output is correct
7 Correct 3247 ms 122568 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2416 ms 111040 KB Output is correct
2 Correct 2239 ms 95452 KB Output is correct
3 Correct 2027 ms 169604 KB Output is correct
4 Correct 1507 ms 101788 KB Output is correct
5 Correct 2238 ms 99920 KB Output is correct
6 Correct 2302 ms 112216 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2416 ms 111040 KB Output is correct
2 Correct 2239 ms 95452 KB Output is correct
3 Correct 2027 ms 169604 KB Output is correct
4 Correct 1507 ms 101788 KB Output is correct
5 Correct 2238 ms 99920 KB Output is correct
6 Correct 2302 ms 112216 KB Output is correct
7 Correct 2864 ms 158116 KB Output is correct
8 Correct 2810 ms 157480 KB Output is correct
9 Correct 2870 ms 158260 KB Output is correct
10 Correct 2045 ms 183248 KB Output is correct
11 Incorrect 1542 ms 121316 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1080 KB Output is correct
2 Correct 7 ms 696 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3257 ms 124076 KB Output is correct
8 Correct 3166 ms 124360 KB Output is correct
9 Correct 3131 ms 124260 KB Output is correct
10 Correct 1695 ms 113836 KB Output is correct
11 Correct 1487 ms 80700 KB Output is correct
12 Correct 1480 ms 204172 KB Output is correct
13 Correct 3247 ms 122568 KB Output is correct
14 Correct 2416 ms 111040 KB Output is correct
15 Correct 2239 ms 95452 KB Output is correct
16 Correct 2027 ms 169604 KB Output is correct
17 Correct 1507 ms 101788 KB Output is correct
18 Correct 2238 ms 99920 KB Output is correct
19 Correct 2302 ms 112216 KB Output is correct
20 Correct 2864 ms 158116 KB Output is correct
21 Correct 2810 ms 157480 KB Output is correct
22 Correct 2870 ms 158260 KB Output is correct
23 Correct 2045 ms 183248 KB Output is correct
24 Incorrect 1542 ms 121316 KB Output isn't correct
25 Halted 0 ms 0 KB -