제출 #382211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382211		rainboy	새 집 (APIO18_new_home)	C11	100 / 100	2768 ms	89692 KiB

new_home

/* https://oj.uz/submission/66480 (Benq) */
#include <stdio.h>
#include <string.h>

#define N	300000
#define K	N
#define Q	300000
#define M	(N * 2 + Q)
#define Q_	(N * 3 + K)
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(Q))) */
#define INF	0x3f3f3f3f
#define X	100000000

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

unsigned int Z = 12345;

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

int xx[N + K], gg[N], yy[Q], tt[N * 2 + Q], n, k, q;

int compare_t(int h1, int h2) {
	int type1, type2;

	if (tt[h1] != tt[h2])
		return tt[h1] - tt[h2];
	type1 = h1 < n * 2 ? ((h1 & 1) == 0 ? 1 : -1) : 0;
	type2 = h2 < n * 2 ? ((h2 & 1) == 0 ? 1 : -1) : 0;
	return type2 - type1;
}

int *yy_, *ll_, *rr_, *xx_;

int compare_y(int h1, int h2) {
	return yy_[h1] - yy_[h2];
}

int (*compare)(int, int);

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) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				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 zz[1 + N + K], ll[1 + N + K], rr[1 + N + K], ii[1 + N + K], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_(), ii[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = xx[ii[u]] != xx[i] ? xx[ii[u]] - xx[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int yyy[2][Q_], lll[2][Q_], rrr[2][Q_], xxx[2][Q_], q_;

void add_event(int x1, int x2, int l, int r) {
	int y;

	if (x1 == x2 || l > r)
		return;
	y = (x1 + x2) / 2;
	yyy[0][q_] = y, lll[0][q_] = l, rrr[0][q_] = r, xxx[0][q_] = x1;
	yyy[1][q_] = -(y + 1), lll[1][q_] = l, rrr[1][q_] = r, xxx[1][q_] = -x2;
	q_++;
}

int st[N_ * 2], n_;

void update(int l, int r, int x) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = min(st[l], x), l++;
		if ((r & 1) == 0)
			st[r] = min(st[r], x), r--;
	}
}

int query(int i) {
	int x = INF;

	for (i += n_; i > 0; i >>= 1)
		x = min(x, st[i]);
	return x;
}

int main() {
	static int hh[M], hh_[Q_], tr[K], ll1[N + K], ii_[Q], ans[Q];
	int m, g, h, h_, h1, h2, i, i_, t, tmp;

	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d%d%d", &xx[i], &gg[i], &tt[i << 1 | 0], &tt[i << 1 | 1]), gg[i]--;
	for (h = 0; h < q; h++)
		scanf("%d%d", &yy[h], &tt[n * 2 + h]);
	m = n * 2 + q;
	for (h = 0; h < m; h++)
		hh[h] = h;
	compare = compare_t, sort(hh, 0, m);
	for (g = 0; g < k; g++) {
		xx[n + g] = -INF;
		tr[g] = node(n + g);
	}
	q_ = 0, i_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (h_ >= n * 2) {
			h_ -= n * 2;
			ii_[h_] = i_++;
		} else {
			int l, r;

			i = h_ >> 1, g = gg[i];
			split(tr[g], i);
			l = ii[last(l_)], r = r_ ? ii[first(r_)] : -1;
			if ((h_ & 1) == 0) {
				add_event(xx[l], r == -1 ? INF : xx[r], ll1[l], i_ - 1);
				ll1[l] = ll1[i] = i_;
				tr[g] = merge(merge(l_, node(i)), r_);
			} else {
				add_event(xx[l], xx[i], ll1[l], i_ - 1), add_event(xx[i], r == -1 ? INF : xx[r], ll1[i], i_ - 1);
				ll1[l] = i_;
				tr[g] = merge(l_, r_);
			}
		}
	}
	for (g = 0; g < k; g++)
		add_event(-INF, INF, ll1[n + g], i_ - 1);
	for (h = 0; h < q; h++)
		hh[h] = h;
	for (h_ = 0; h_ < q_; h_++)
		hh_[h_] = h_;
	compare = compare_y;
	yy_ = yy, sort(hh, 0, q);
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (t = 0; t < 2; t++) {
		yy_ = yyy[t], ll_ = lll[t], rr_ = rrr[t], xx_ = xxx[t], sort(hh_, 0, q_);
		memset(st, 0x3f, n_ * 2 * sizeof *st);
		for (h = q - 1, h_ = q_ - 1; h >= 0; h--) {
			while (h_ >= 0 && yy_[hh_[h_]] >= yy[hh[h]]) {
				int h1 = hh_[h_--];

				update(ll_[h1], rr_[h1], xx_[h1]);
			}
			ans[hh[h]] = max(ans[hh[h]], yy[hh[h]] - query(ii_[hh[h]]));
		}
		for (h = 0; h < q; h++)
			yy[h] = -yy[h];
		for (h1 = 0, h2 = q - 1; h1 < h2; h1++, h2--)
			tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h] > X ? -1 : ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.c: In function 'main':
new_home.c:152:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:154:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  154 |   scanf("%d%d%d%d", &xx[i], &gg[i], &tt[i << 1 | 0], &tt[i << 1 | 1]), gg[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:156:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  156 |   scanf("%d%d", &yy[h], &tt[n * 2 + h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20