Submission #527566

#	Time	Username	Problem	Language	Result	Execution time	Memory
527566		rainboy	도로 건설 사업 (JOI13_construction)	C11	70 / 100	1291 ms	33092 KiB

construction

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

#define N	300000
#define K	300000
#define N1	(N + K * 2)
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(N1))) */
#define M	(N * 2)

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

unsigned int X = 12345;

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

int xx[N1], xx_[N1], yy[N1], yy_[N1], n, n1, k;
int uu[M], vv[M], ww[M], m, m_; long long ss[M];

int type(int i) {
	return i < n ? 1 : ((i - n & 1) == 0 ? 0 : 2);
}

int compare_x_(int i, int j) {
	return xx_[i] - xx_[j];
}

int compare_xty(int i, int j) {
	int ti, tj;

	if (xx[i] != xx[j])
		return xx[i] - xx[j];
	ti = type(i), tj = type(j);
	if (ti != tj)
		return ti - tj;
	return yy[i] - yy[j];
}

int compare_w(int h1, int h2) {
	return ww[h1] - ww[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 ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int st[N_ * 2], lz[N_], h_, n_;

void put(int i, int x) {
	st[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i])
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

int query(int l, int r) {
	int x;

	push(l += n_), push(r += n_);
	x = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = max(x, st[l++]);
		if ((r & 1) == 0)
			x = max(x, st[r--]);
	}
	return x;
}

int main() {
	static int ii[N1], hh[M];
	int q, h, i, r, x, tmp;

	scanf("%d%d%d", &n, &k, &q), n1 = n + k * 2;
	for (i = 0; i < n1; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		xx_[i] = xx[i], yy_[i] = yy[i];
	}
	for (r = 0; r < 2; r++) {
		for (i = 0; i < n1; i++)
			ii[i] = i;
		compare = compare_x_, sort(ii, 0, n1);
		for (i = 0, x = 0; i < n1; i++)
			xx_[ii[i]] = i + 1 == n1 || xx_[ii[i + 1]] != xx_[ii[i]] ? x++ : x;
		for (i = 0; i < n1; i++)
			tmp = xx_[i], xx_[i] = yy_[i], yy_[i] = tmp;
	}
	h_ = 0;
	while (1 << h_ < n1)
		h_++;
	n_ = 1 << h_;
	for (r = 0; r < 2; r++) {
		for (i = 0; i < n1; i++)
			ii[i] = i;
		compare = compare_xty, sort(ii, 0, n1);
		memset(st, 0, n_ * 2 * sizeof *st), memset(lz, 0, n_ * sizeof *lz);
		for (i = 0; i < n1; i++) {
			int u = ii[i], v = i + 1 == n1 ? -1 : ii[i + 1];

			if (type(u) == 0)
				update(yy_[u], yy_[u ^ 1], 1);
			else if (type(u) == 2)
				update(yy_[u ^ 1], yy_[u], -1);
			else if (i + 1 < n1 && xx[v] == xx[u] && type(v) == 1 && query(yy_[u], yy_[v]) == 0)
				uu[m] = u, vv[m] = v, ww[m] = yy[v] - yy[u], m++;
		}
		for (i = 0; i < n1; i++) {
			tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
			tmp = xx_[i], xx_[i] = yy_[i], yy_[i] = tmp;
		}
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	compare = compare_w, sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < m; h++)
		if (join(uu[hh[h]], vv[hh[h]]))
			hh[m_++] = hh[h];
	m = m_;
	for (h = 0; h < m; h++)
		ss[h] = (h == 0 ? 0 : ss[h - 1]) + ww[hh[h]];
	while (q--) {
		int w, c;

		scanf("%d%d", &w, &c);
		if (c < n - m)
			printf("-1\n");
		else {
			int lower, upper;

			lower = n - c - 1, upper = m;
			while (upper - lower > 1) {
				h = (lower + upper) / 2;
				if (ww[hh[h]] > w)
					upper = h;
				else
					lower = h;
			}
			printf("%lld\n", (lower == -1 ? 0 : ss[lower]) + (long long) (n - upper) * w);
		}
	}
	return 0;
}

Compilation message (stderr)

construction.c: In function 'type':
construction.c:22:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  return i < n ? 1 : ((i - n & 1) == 0 ? 0 : 2);
      |                       ~~^~~
construction.c: In function 'main':
construction.c:150:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d%d%d", &n, &k, &q), n1 = n + k * 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:201:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |   scanf("%d%d", &w, &c);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30