oj.uz

Submission #527565

# Submission time Handle Problem Language Result Execution time Memory
527565 2022-02-17T16:28:30 Z rainboy 도로 건설 사업 (JOI13_construction) C
70 / 100
 1177 ms 52688 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 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 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:23:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |  return i < n ? 1 : ((i - n & 1) == 0 ? 0 : 2);
      |                       ~~^~~
construction.c: In function 'main':
construction.c:151:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |  scanf("%d%d%d", &n, &k, &q), n1 = n + k * 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:153:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.c:202:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |   scanf("%d%d", &w, &c);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1176 KB Output is correct
2 Correct 239 ms 11332 KB Output is correct
3 Correct 237 ms 11408 KB Output is correct
4 Correct 237 ms 16628 KB Output is correct
5 Correct 256 ms 13640 KB Output is correct
6 Correct 238 ms 11548 KB Output is correct
7 Correct 136 ms 16812 KB Output is correct
8 Correct 196 ms 13648 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1176 KB Output is correct
2 Correct 239 ms 11332 KB Output is correct
3 Correct 237 ms 11408 KB Output is correct
4 Correct 237 ms 16628 KB Output is correct
5 Correct 256 ms 13640 KB Output is correct
6 Correct 238 ms 11548 KB Output is correct
7 Correct 136 ms 16812 KB Output is correct
8 Correct 196 ms 13648 KB Output is correct
9 Correct 1036 ms 26144 KB Output is correct
10 Correct 1002 ms 26288 KB Output is correct
11 Correct 982 ms 26184 KB Output is correct
12 Correct 996 ms 26088 KB Output is correct
13 Correct 743 ms 26848 KB Output is correct
14 Correct 256 ms 16664 KB Output is correct
15 Correct 967 ms 36916 KB Output is correct
16 Correct 460 ms 41416 KB Output is correct
17 Correct 448 ms 39072 KB Output is correct
18 Correct 748 ms 39152 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1176 KB Output is correct
2 Correct 239 ms 11332 KB Output is correct
3 Correct 237 ms 11408 KB Output is correct
4 Correct 237 ms 16628 KB Output is correct
5 Correct 256 ms 13640 KB Output is correct
6 Correct 238 ms 11548 KB Output is correct
7 Correct 136 ms 16812 KB Output is correct
8 Correct 196 ms 13648 KB Output is correct
9 Correct 492 ms 18984 KB Output is correct
10 Correct 507 ms 17780 KB Output is correct
11 Correct 481 ms 16448 KB Output is correct
12 Correct 526 ms 20480 KB Output is correct
13 Correct 365 ms 12880 KB Output is correct
14 Correct 584 ms 19668 KB Output is correct
15 Correct 532 ms 18624 KB Output is correct
16 Correct 515 ms 18076 KB Output is correct
17 Correct 378 ms 21700 KB Output is correct
18 Correct 555 ms 18500 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1176 KB Output is correct
2 Correct 239 ms 11332 KB Output is correct
3 Correct 237 ms 11408 KB Output is correct
4 Correct 237 ms 16628 KB Output is correct
5 Correct 256 ms 13640 KB Output is correct
6 Correct 238 ms 11548 KB Output is correct
7 Correct 136 ms 16812 KB Output is correct
8 Correct 196 ms 13648 KB Output is correct
9 Correct 1036 ms 26144 KB Output is correct
10 Correct 1002 ms 26288 KB Output is correct
11 Correct 982 ms 26184 KB Output is correct
12 Correct 996 ms 26088 KB Output is correct
13 Correct 743 ms 26848 KB Output is correct
14 Correct 256 ms 16664 KB Output is correct
15 Correct 967 ms 36916 KB Output is correct
16 Correct 460 ms 41416 KB Output is correct
17 Correct 448 ms 39072 KB Output is correct
18 Correct 748 ms 39152 KB Output is correct
19 Correct 492 ms 18984 KB Output is correct
20 Correct 507 ms 17780 KB Output is correct
21 Correct 481 ms 16448 KB Output is correct
22 Correct 526 ms 20480 KB Output is correct
23 Correct 365 ms 12880 KB Output is correct
24 Correct 584 ms 19668 KB Output is correct
25 Correct 532 ms 18624 KB Output is correct
26 Correct 515 ms 18076 KB Output is correct
27 Correct 378 ms 21700 KB Output is correct
28 Correct 555 ms 18500 KB Output is correct
29 Correct 1177 ms 52688 KB Output is correct
30 Correct 699 ms 31048 KB Output is correct
31 Correct 1112 ms 46072 KB Output is correct
32 Correct 370 ms 21416 KB Output is correct
33 Correct 1108 ms 46412 KB Output is correct
34 Incorrect 388 ms 22372 KB Output isn't correct
35 Halted 0 ms 0 KB -