Submission #670010

#	Time	Username	Problem	Language	Result	Execution time	Memory
670010		rainboy	Sweeping (JOI20_sweeping)	C11	10 / 100	3589 ms	224428 KiB

sweeping

#include <stdio.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];
int ll1[N], rr1[N];

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 (q == 0 || m == 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] : m;
		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] : m;
		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] == m && qq[g] == m)
			g_ = g;
		else if (qq[g] == m || pp[g] < m && 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", &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]);
			if (tt[h] == 2)
				zz[h] = s - 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 'solve_':
sweeping.c:166:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  166 |   else if (qq[g] == m || pp[g] < m && 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", &xx[i], &yy[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:214:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |    scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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