oj.uz

Submission #527566

# Submission time Handle Problem Language Result Execution time Memory
527566 2022-02-17T16:31:50 Z rainboy 도로 건설 사업 (JOI13_construction) C
70 / 100
 1291 ms 33092 KB 
#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

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 18 ms 844 KB Output is correct
2 Correct 230 ms 10512 KB Output is correct
3 Correct 235 ms 10580 KB Output is correct
4 Correct 237 ms 15884 KB Output is correct
5 Correct 258 ms 12928 KB Output is correct
6 Correct 233 ms 10680 KB Output is correct
7 Correct 130 ms 16000 KB Output is correct
8 Correct 191 ms 12868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 844 KB Output is correct
2 Correct 230 ms 10512 KB Output is correct
3 Correct 235 ms 10580 KB Output is correct
4 Correct 237 ms 15884 KB Output is correct
5 Correct 258 ms 12928 KB Output is correct
6 Correct 233 ms 10680 KB Output is correct
7 Correct 130 ms 16000 KB Output is correct
8 Correct 191 ms 12868 KB Output is correct
9 Correct 953 ms 25280 KB Output is correct
10 Correct 952 ms 25288 KB Output is correct
11 Correct 966 ms 25360 KB Output is correct
12 Correct 978 ms 25232 KB Output is correct
13 Correct 792 ms 25924 KB Output is correct
14 Correct 252 ms 12868 KB Output is correct
15 Correct 986 ms 25288 KB Output is correct
16 Correct 461 ms 33092 KB Output is correct
17 Correct 505 ms 30676 KB Output is correct
18 Correct 775 ms 27560 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 844 KB Output is correct
2 Correct 230 ms 10512 KB Output is correct
3 Correct 235 ms 10580 KB Output is correct
4 Correct 237 ms 15884 KB Output is correct
5 Correct 258 ms 12928 KB Output is correct
6 Correct 233 ms 10680 KB Output is correct
7 Correct 130 ms 16000 KB Output is correct
8 Correct 191 ms 12868 KB Output is correct
9 Correct 497 ms 18188 KB Output is correct
10 Correct 488 ms 16964 KB Output is correct
11 Correct 473 ms 14984 KB Output is correct
12 Correct 548 ms 19872 KB Output is correct
13 Correct 429 ms 12136 KB Output is correct
14 Correct 669 ms 19072 KB Output is correct
15 Correct 620 ms 18904 KB Output is correct
16 Correct 559 ms 18464 KB Output is correct
17 Correct 457 ms 22056 KB Output is correct
18 Correct 665 ms 18896 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 844 KB Output is correct
2 Correct 230 ms 10512 KB Output is correct
3 Correct 235 ms 10580 KB Output is correct
4 Correct 237 ms 15884 KB Output is correct
5 Correct 258 ms 12928 KB Output is correct
6 Correct 233 ms 10680 KB Output is correct
7 Correct 130 ms 16000 KB Output is correct
8 Correct 191 ms 12868 KB Output is correct
9 Correct 953 ms 25280 KB Output is correct
10 Correct 952 ms 25288 KB Output is correct
11 Correct 966 ms 25360 KB Output is correct
12 Correct 978 ms 25232 KB Output is correct
13 Correct 792 ms 25924 KB Output is correct
14 Correct 252 ms 12868 KB Output is correct
15 Correct 986 ms 25288 KB Output is correct
16 Correct 461 ms 33092 KB Output is correct
17 Correct 505 ms 30676 KB Output is correct
18 Correct 775 ms 27560 KB Output is correct
19 Correct 497 ms 18188 KB Output is correct
20 Correct 488 ms 16964 KB Output is correct
21 Correct 473 ms 14984 KB Output is correct
22 Correct 548 ms 19872 KB Output is correct
23 Correct 429 ms 12136 KB Output is correct
24 Correct 669 ms 19072 KB Output is correct
25 Correct 620 ms 18904 KB Output is correct
26 Correct 559 ms 18464 KB Output is correct
27 Correct 457 ms 22056 KB Output is correct
28 Correct 665 ms 18896 KB Output is correct
29 Correct 1291 ms 32860 KB Output is correct
30 Correct 733 ms 17272 KB Output is correct
31 Correct 1238 ms 26876 KB Output is correct
32 Correct 357 ms 11200 KB Output is correct
33 Correct 1148 ms 26720 KB Output is correct
34 Incorrect 397 ms 10680 KB Output isn't correct
35 Halted 0 ms 0 KB -