oj.uz

Submission #381230

# Submission time Handle Problem Language Result Execution time Memory
381230 2021-03-24T20:28:49 Z rainboy New Home (APIO18_new_home) C
12 / 100
 5000 ms 42944 KB 
#include <stdio.h>

#define N	300000
#define Q	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(Q))) */
#define INF	0x3f3f3f3f

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[N], gg[N], tt[N * 2 + Q], n;
int yy[Q], q;

int compare1(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 compare2(int h1, int h2) {
	return yy[h1] - yy[h2];
}

int compare3(int i, int j) {
	return gg[i] != gg[j] ? gg[i] - gg[j] : xx[i] - xx[j];
}

int (*compare)(int, int);

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(hh[j], h);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int zz[1 + N], ll[1 + N], rr[1 + N], ii_[1 + N], 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 tr_update(int u, int i) {
	split(u, i);
	return merge(merge(l_, u_ == 0 ? node(i) : 0), r_);
}

int tr_query(int u, int x) {
	int d;

	d = INF;
	while (u)
		if (xx[ii_[u]] < x)
			d = min(d, x - xx[ii_[u]]), u = rr[u];
		else
			d = min(d, xx[ii_[u]] - x), u = ll[u];
	return d;
}

int hh[N * 2 + Q]; 

int search(int x) {
	int lower = -1, upper = q;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (yy[hh[h]] * 2 <= x)
			lower = h;
		else
			upper = h;
	}
	return lower;
}

int stmn[N_ * 2], stmx[N_ * 2], n_;

void build() {
	int i;

	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (i = 1; i < n_ * 2; i++)
		stmn[i] = INF, stmx[i] = -INF;
}

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

int query(int i) {
	int y, l, r;

	l = r = y = yy[hh[i]];
	for (i += n_; i > 0; i >>= 1)
		l = min(l, stmn[i]), r = max(r, stmx[i]);
	return max(y - l, r - y);
}

int main() {
	static int ll_[N], rr_[N], ii[N], tr[N], ans[Q];
	int k, g, h, i;

	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]);
	if (k <= 400) {
		for (h = 0; h < n * 2 + q; h++)
			hh[h] = h;
		compare = compare1, sort(hh, 0, n * 2 + q);
		for (h = 0; h < n * 2 + q; h++) {
			int h_ = hh[h];

			if (h_ >= n * 2) {
				h_ -= n * 2;
				for (g = 0; g < k; g++)
					ans[h_] = max(ans[h_], tr_query(tr[g], yy[h_]));
				if (ans[h_] == INF)
					ans[h_] = -1;
			} else {
				i = h_ >> 1;
				tr[gg[i]] = tr_update(tr[gg[i]], i);
			}
		}
	} else {
		for (h = 0; h < q; h++)
			hh[h] = h;
		compare = compare2, sort(hh, 0, q);
		for (i = 0; i < n; i++) {
			tr[gg[i]] = tr_update(tr[gg[i]], i);
			ii[i] = i;
		}
		compare = compare3, sort(ii, 0, n);
		ll_[0] = 0, rr_[n - 1] = q - 1;
		for (h = 0; h + 1 < n; h++)
			if (gg[ii[h]] == gg[ii[h + 1]]) {
				int h_ = search(xx[ii[h]] + xx[ii[h + 1]]);

				rr_[h] = h_, ll_[h + 1] = h_ + 1;
			} else
				rr_[h] = q - 1, ll_[h + 1] = 0;
		build();
		for (h = 0; h < n; h++)
			if (ll_[h] <= rr_[h])
				update(ll_[h], rr_[h], xx[ii[h]]);
		for (h = 0; h < q; h++)
			ans[hh[h]] = query(h);
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 3750 ms 4108 KB Output is correct
32 Correct 149 ms 3820 KB Output is correct
33 Correct 319 ms 4076 KB Output is correct
34 Correct 2624 ms 4320 KB Output is correct
35 Correct 1819 ms 4108 KB Output is correct
36 Correct 369 ms 4076 KB Output is correct
37 Correct 256 ms 4076 KB Output is correct
38 Correct 162 ms 4076 KB Output is correct
39 Correct 122 ms 4076 KB Output is correct
40 Correct 127 ms 4140 KB Output is correct
41 Correct 289 ms 4332 KB Output is correct
42 Correct 366 ms 4076 KB Output is correct
43 Correct 620 ms 4204 KB Output is correct
44 Correct 260 ms 4264 KB Output is correct
45 Correct 140 ms 4204 KB Output is correct
46 Correct 96 ms 4204 KB Output is correct
47 Correct 87 ms 3820 KB Output is correct
48 Correct 84 ms 3948 KB Output is correct
49 Correct 99 ms 3948 KB Output is correct
50 Correct 220 ms 3948 KB Output is correct
51 Correct 94 ms 4076 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 29148 KB Output is correct
2 Correct 3485 ms 30788 KB Output is correct
3 Correct 426 ms 41676 KB Output is correct
4 Correct 614 ms 42860 KB Output is correct
5 Correct 1290 ms 30396 KB Output is correct
6 Correct 2307 ms 30984 KB Output is correct
7 Correct 404 ms 41520 KB Output is correct
8 Correct 513 ms 42944 KB Output is correct
9 Correct 542 ms 42604 KB Output is correct
10 Execution timed out 5052 ms 29916 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 28652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 3750 ms 4108 KB Output is correct
32 Correct 149 ms 3820 KB Output is correct
33 Correct 319 ms 4076 KB Output is correct
34 Correct 2624 ms 4320 KB Output is correct
35 Correct 1819 ms 4108 KB Output is correct
36 Correct 369 ms 4076 KB Output is correct
37 Correct 256 ms 4076 KB Output is correct
38 Correct 162 ms 4076 KB Output is correct
39 Correct 122 ms 4076 KB Output is correct
40 Correct 127 ms 4140 KB Output is correct
41 Correct 289 ms 4332 KB Output is correct
42 Correct 366 ms 4076 KB Output is correct
43 Correct 620 ms 4204 KB Output is correct
44 Correct 260 ms 4264 KB Output is correct
45 Correct 140 ms 4204 KB Output is correct
46 Correct 96 ms 4204 KB Output is correct
47 Correct 87 ms 3820 KB Output is correct
48 Correct 84 ms 3948 KB Output is correct
49 Correct 99 ms 3948 KB Output is correct
50 Correct 220 ms 3948 KB Output is correct
51 Correct 94 ms 4076 KB Output is correct
52 Incorrect 88 ms 5228 KB Output isn't correct
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 3750 ms 4108 KB Output is correct
32 Correct 149 ms 3820 KB Output is correct
33 Correct 319 ms 4076 KB Output is correct
34 Correct 2624 ms 4320 KB Output is correct
35 Correct 1819 ms 4108 KB Output is correct
36 Correct 369 ms 4076 KB Output is correct
37 Correct 256 ms 4076 KB Output is correct
38 Correct 162 ms 4076 KB Output is correct
39 Correct 122 ms 4076 KB Output is correct
40 Correct 127 ms 4140 KB Output is correct
41 Correct 289 ms 4332 KB Output is correct
42 Correct 366 ms 4076 KB Output is correct
43 Correct 620 ms 4204 KB Output is correct
44 Correct 260 ms 4264 KB Output is correct
45 Correct 140 ms 4204 KB Output is correct
46 Correct 96 ms 4204 KB Output is correct
47 Correct 87 ms 3820 KB Output is correct
48 Correct 84 ms 3948 KB Output is correct
49 Correct 99 ms 3948 KB Output is correct
50 Correct 220 ms 3948 KB Output is correct
51 Correct 94 ms 4076 KB Output is correct
52 Correct 612 ms 29148 KB Output is correct
53 Correct 3485 ms 30788 KB Output is correct
54 Correct 426 ms 41676 KB Output is correct
55 Correct 614 ms 42860 KB Output is correct
56 Correct 1290 ms 30396 KB Output is correct
57 Correct 2307 ms 30984 KB Output is correct
58 Correct 404 ms 41520 KB Output is correct
59 Correct 513 ms 42944 KB Output is correct
60 Correct 542 ms 42604 KB Output is correct
61 Execution timed out 5052 ms 29916 KB Time limit exceeded
62 Halted 0 ms 0 KB -