oj.uz

Submission #527568

# Submission time Handle Problem Language Result Execution time Memory
527568 2022-02-17T16:39:11 Z rainboy 도로 건설 사업 (JOI13_construction) C
100 / 100
 1185 ms 52944 KB 
#include <stdio.h>
#include <string.h>

#define N	200000
#define K	200000
#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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1212 KB Output is correct
2 Correct 265 ms 11224 KB Output is correct
3 Correct 237 ms 11364 KB Output is correct
4 Correct 235 ms 16648 KB Output is correct
5 Correct 268 ms 13692 KB Output is correct
6 Correct 252 ms 11408 KB Output is correct
7 Correct 148 ms 16784 KB Output is correct
8 Correct 195 ms 13668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1212 KB Output is correct
2 Correct 265 ms 11224 KB Output is correct
3 Correct 237 ms 11364 KB Output is correct
4 Correct 235 ms 16648 KB Output is correct
5 Correct 268 ms 13692 KB Output is correct
6 Correct 252 ms 11408 KB Output is correct
7 Correct 148 ms 16784 KB Output is correct
8 Correct 195 ms 13668 KB Output is correct
9 Correct 982 ms 26092 KB Output is correct
10 Correct 966 ms 25984 KB Output is correct
11 Correct 1012 ms 26028 KB Output is correct
12 Correct 981 ms 26016 KB Output is correct
13 Correct 743 ms 26692 KB Output is correct
14 Correct 257 ms 13380 KB Output is correct
15 Correct 992 ms 25716 KB Output is correct
16 Correct 462 ms 33508 KB Output is correct
17 Correct 464 ms 33700 KB Output is correct
18 Correct 776 ms 28280 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1212 KB Output is correct
2 Correct 265 ms 11224 KB Output is correct
3 Correct 237 ms 11364 KB Output is correct
4 Correct 235 ms 16648 KB Output is correct
5 Correct 268 ms 13692 KB Output is correct
6 Correct 252 ms 11408 KB Output is correct
7 Correct 148 ms 16784 KB Output is correct
8 Correct 195 ms 13668 KB Output is correct
9 Correct 533 ms 19036 KB Output is correct
10 Correct 505 ms 17736 KB Output is correct
11 Correct 470 ms 16240 KB Output is correct
12 Correct 501 ms 20680 KB Output is correct
13 Correct 367 ms 12964 KB Output is correct
14 Correct 617 ms 19760 KB Output is correct
15 Correct 528 ms 18120 KB Output is correct
16 Correct 512 ms 17352 KB Output is correct
17 Correct 382 ms 20932 KB Output is correct
18 Correct 539 ms 17912 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1212 KB Output is correct
2 Correct 265 ms 11224 KB Output is correct
3 Correct 237 ms 11364 KB Output is correct
4 Correct 235 ms 16648 KB Output is correct
5 Correct 268 ms 13692 KB Output is correct
6 Correct 252 ms 11408 KB Output is correct
7 Correct 148 ms 16784 KB Output is correct
8 Correct 195 ms 13668 KB Output is correct
9 Correct 982 ms 26092 KB Output is correct
10 Correct 966 ms 25984 KB Output is correct
11 Correct 1012 ms 26028 KB Output is correct
12 Correct 981 ms 26016 KB Output is correct
13 Correct 743 ms 26692 KB Output is correct
14 Correct 257 ms 13380 KB Output is correct
15 Correct 992 ms 25716 KB Output is correct
16 Correct 462 ms 33508 KB Output is correct
17 Correct 464 ms 33700 KB Output is correct
18 Correct 776 ms 28280 KB Output is correct
19 Correct 533 ms 19036 KB Output is correct
20 Correct 505 ms 17736 KB Output is correct
21 Correct 470 ms 16240 KB Output is correct
22 Correct 501 ms 20680 KB Output is correct
23 Correct 367 ms 12964 KB Output is correct
24 Correct 617 ms 19760 KB Output is correct
25 Correct 528 ms 18120 KB Output is correct
26 Correct 512 ms 17352 KB Output is correct
27 Correct 382 ms 20932 KB Output is correct
28 Correct 539 ms 17912 KB Output is correct
29 Correct 1185 ms 32864 KB Output is correct
30 Correct 653 ms 16580 KB Output is correct
31 Correct 1099 ms 26784 KB Output is correct
32 Correct 360 ms 10436 KB Output is correct
33 Correct 1141 ms 26744 KB Output is correct
34 Correct 357 ms 10264 KB Output is correct
35 Correct 1018 ms 46116 KB Output is correct
36 Correct 1162 ms 50836 KB Output is correct
37 Correct 712 ms 52944 KB Output is correct
38 Correct 951 ms 48360 KB Output is correct
39 Correct 575 ms 28172 KB Output is correct