oj.uz

Submission #381249

# Submission time Handle Problem Language Result Execution time Memory
381249 2021-03-24T22:57:29 Z rainboy New Home (APIO18_new_home) C
57 / 100
 5000 ms 194368 KB 
#include <stdio.h>
#include <stdlib.h>
 
#define N	300000
#define Q	300000
#define L_	19	/* L_ = ceil(log2(Q)) */
#define N_	(1 << L_)
#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], n;
int yy[Q], yy_[Q], tt_[Q], tt1[Q], q_;
 
int compareh_y(int h1, int h2) {
	return yy[h1] - yy[h2];
}
 
int compareh_t(int h1, int h2) {
	return tt_[h1] - tt_[h2];
}
 
int compare_i(int i, int j) {
	return gg[i] != gg[j] ? gg[i] - gg[j] : xx[i] - xx[j];
}
 
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 idx(int *xx, int x) {
	int lower = -1, upper = q_;
 
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;
 
		if (xx[h] <= x)
			lower = h;
		else
			upper = h;
	}
	return lower;
}
 
int stmn[N_ * 2], stmx[N_ * 2], *ei[N_ * 2], eo[N_ * 2], n_;
char upd[L_ + 2][N_ * 2]; int qu[L_ + 2][N_ * 2], cnt[L_ + 2];
int oldmn[L_ + 2][N_ * 2], oldmx[L_ + 2][N_ * 2];
 
void push(int i, int x, int t) {
	if (!upd[t][i]) {
		upd[t][i] = 1, qu[t][cnt[t]++] = i;
		oldmn[t][i] = stmn[i], oldmx[t][i] = stmx[i];
	}
	stmn[i] = min(stmn[i], x);
	stmx[i] = max(stmx[i], x);
}
 
void pop(int t) {
	while (cnt[t]--) {
		int i = qu[t][cnt[t]];

		upd[t][i] = 0;
		stmn[i] = oldmn[t][i], stmx[i] = oldmx[t][i];
	}
	cnt[t] = 0;
}

void build() {
	int i;
 
	n_ = 1;
	while (n_ < q_)
		n_ <<= 1;
	for (i = 1; i < n_ * 2; i++)
		stmn[i] = INF, stmx[i] = -INF;
	for (i = 1; i < n_ * 2; i++)
		ei[i] = (int *) malloc(2 * sizeof *ei[i]);
}
 
void update(int l, int r, int x, int t) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			push(l++, x, t);
		if ((r & 1) == 0)
			push(r--, x, t);
	}
}
 
int query(int i) {
	int y, l, r;
 
	l = r = y = yy_[i];
	for (i += n_; i > 0; i >>= 1)
		l = min(l, stmn[i]), r = max(r, stmx[i]);
	return l == -INF || r == INF ? -1 : max(y - l, r - y);
}
 
int mid(int a, int b) {
	return a + b > 0 ? (a + b) / 2 : -(-a + b + 1) / 2;
}
 
int pp[N], qq[N];
 
void remove_(int i, int t) {
	int p = pp[i], q = qq[i];
 
	if (p != -1)
		qq[p] = q;
	if (q != -1)
		pp[q] = p;
	if (p == -1 && q == -1)
		update(0, q_ - 1, INF, t), update(0, q_ - 1, -INF, t);
	else if (p == -1)
		update(0, idx(yy_, xx[q]), xx[q], t);
	else if (q == -1)
		update(idx(yy_, xx[p] - 1) + 1, q_ - 1, xx[p], t);
	else {
		int l = idx(yy_, xx[p] - 1) + 1, h = idx(yy_, mid(xx[p], xx[q])), r = idx(yy_, xx[q]);
 
		update(l, h, xx[p], t), update(h + 1, r, xx[q], t);
	}
}
 
void add(int i) {
	int p = pp[i], q = qq[i];
 
	if (p != -1)
		qq[p] = i;
	if (q != -1)
		pp[q] = i;
}
 
void append_(int i, int i_) {
	int o = eo[i]++;
 
	if (o >= 2 && (o & o - 1) == 0)
		ei[i] = (int *) realloc(ei[i], o * 2 * sizeof *ei[i]);
	ei[i][o] = i_;
}
 
void update_(int l, int r, int i_) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			append_(l++, i_);
		if ((r & 1) == 0)
			append_(r--, i_);
	}
}
 
int hh[Q], inv[Q], ans[Q];
 
void solve(int i, int t) {
	int o;
 
	for (o = eo[i]; o--; ) {
		int i_ = ei[i][o];
 
		remove_(i_, t);
	}
	if (i >= n_) {
		int h = i - n_;
 
		if (h < q_)
			ans[hh[h]] = query(inv[hh[h]]);
	} else
		solve(i << 1 | 0, t + 1), solve(i << 1 | 1, t + 1);
	for (o = 0; o < eo[i]; o++) {
		int i_ = ei[i][o];
 
		add(i_);
	}
	pop(t);
}
 
int main() {
	static int tt[N * 2], ii[N], ll[N], rr[N];
	static char used[N];
	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]--;
		used[gg[i]] = 1;
	}
	for (g = 0; g < k; g++)
		if (!used[g]) {
			for (h = 0; h < q_; h++)
				printf("-1\n");
			return 0;
		}
	for (h = 0; h < q_; h++)
		scanf("%d%d", &yy[h], &tt_[h]);
	for (h = 0; h < q_; h++)
		hh[h] = h;
	compare = compareh_y, sort(hh, 0, q_);
	for (h = 0; h < q_; h++)
		yy_[h] = yy[hh[h]], inv[hh[h]] = h;
	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_i, sort(ii, 0, n);
	pp[ii[0]] = -1, qq[ii[n - 1]] = -1;
	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_ = idx(yy_, mid(xx[ii[h]], xx[ii[h + 1]]));
 
			qq[ii[h]] = ii[h + 1], pp[ii[h + 1]] = ii[h];
			rr[h] = h_, ll[h + 1] = h_ + 1;
		} else {
			qq[ii[h]] = -1, pp[ii[h + 1]] = -1;
			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]], 0);
	compare = compareh_t, sort(hh, 0, q_);
	for (h = 0; h < q_; h++)
		tt1[h] = tt_[hh[h]];
	for (i = 0; i < n; i++)
		update_(0, idx(tt1, tt[i << 1 | 0] - 1), i), update_(idx(tt1, tt[i << 1 | 1]) + 1, n_ - 1, i);
	solve(1, 1);
	for (h = 0; h < q_; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message

new_home.c: In function 'append_':
new_home.c:163:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  163 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
new_home.c: In function 'main':
new_home.c:207:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  207 |  scanf("%d%d%d", &n, &k, &q_);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:209:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  209 |   scanf("%d%d%d%d", &xx[i], &gg[i], &tt[i << 1 | 0], &tt[i << 1 | 1]), gg[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.c:219:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  219 |   scanf("%d%d", &yy[h], &tt_[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 2 ms 876 KB Output is correct
19 Correct 3 ms 876 KB Output is correct
20 Correct 3 ms 876 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 876 KB Output is correct
24 Correct 3 ms 876 KB Output is correct
25 Correct 3 ms 876 KB Output is correct
26 Correct 3 ms 876 KB Output is correct
27 Correct 2 ms 876 KB Output is correct
28 Correct 2 ms 876 KB Output is correct
29 Correct 3 ms 876 KB Output is correct
30 Correct 2 ms 876 KB Output is correct
31 Correct 1177 ms 36464 KB Output is correct
32 Correct 423 ms 22636 KB Output is correct
33 Correct 971 ms 36096 KB Output is correct
34 Correct 1172 ms 36332 KB Output is correct
35 Correct 1090 ms 36348 KB Output is correct
36 Correct 899 ms 36236 KB Output is correct
37 Correct 722 ms 35444 KB Output is correct
38 Correct 590 ms 35200 KB Output is correct
39 Correct 526 ms 35076 KB Output is correct
40 Correct 519 ms 34996 KB Output is correct
41 Correct 899 ms 35948 KB Output is correct
42 Correct 919 ms 36084 KB Output is correct
43 Correct 156 ms 12488 KB Output is correct
44 Correct 900 ms 36076 KB Output is correct
45 Correct 924 ms 35948 KB Output is correct
46 Correct 941 ms 35692 KB Output is correct
47 Correct 432 ms 34412 KB Output is correct
48 Correct 453 ms 34028 KB Output is correct
49 Correct 493 ms 34668 KB Output is correct
50 Correct 523 ms 35184 KB Output is correct
51 Correct 539 ms 34796 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2629 ms 133632 KB Output is correct
2 Correct 2668 ms 135416 KB Output is correct
3 Correct 938 ms 80500 KB Output is correct
4 Correct 2301 ms 132292 KB Output is correct
5 Correct 2204 ms 132048 KB Output is correct
6 Correct 2529 ms 134948 KB Output is correct
7 Correct 852 ms 80648 KB Output is correct
8 Correct 1846 ms 131944 KB Output is correct
9 Correct 2562 ms 134872 KB Output is correct
10 Correct 2789 ms 135980 KB Output is correct
11 Correct 1578 ms 135184 KB Output is correct
12 Correct 1820 ms 135640 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 194368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 2 ms 876 KB Output is correct
19 Correct 3 ms 876 KB Output is correct
20 Correct 3 ms 876 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 876 KB Output is correct
24 Correct 3 ms 876 KB Output is correct
25 Correct 3 ms 876 KB Output is correct
26 Correct 3 ms 876 KB Output is correct
27 Correct 2 ms 876 KB Output is correct
28 Correct 2 ms 876 KB Output is correct
29 Correct 3 ms 876 KB Output is correct
30 Correct 2 ms 876 KB Output is correct
31 Correct 1177 ms 36464 KB Output is correct
32 Correct 423 ms 22636 KB Output is correct
33 Correct 971 ms 36096 KB Output is correct
34 Correct 1172 ms 36332 KB Output is correct
35 Correct 1090 ms 36348 KB Output is correct
36 Correct 899 ms 36236 KB Output is correct
37 Correct 722 ms 35444 KB Output is correct
38 Correct 590 ms 35200 KB Output is correct
39 Correct 526 ms 35076 KB Output is correct
40 Correct 519 ms 34996 KB Output is correct
41 Correct 899 ms 35948 KB Output is correct
42 Correct 919 ms 36084 KB Output is correct
43 Correct 156 ms 12488 KB Output is correct
44 Correct 900 ms 36076 KB Output is correct
45 Correct 924 ms 35948 KB Output is correct
46 Correct 941 ms 35692 KB Output is correct
47 Correct 432 ms 34412 KB Output is correct
48 Correct 453 ms 34028 KB Output is correct
49 Correct 493 ms 34668 KB Output is correct
50 Correct 523 ms 35184 KB Output is correct
51 Correct 539 ms 34796 KB Output is correct
52 Correct 265 ms 16912 KB Output is correct
53 Correct 296 ms 16360 KB Output is correct
54 Correct 694 ms 35692 KB Output is correct
55 Correct 684 ms 35180 KB Output is correct
56 Correct 569 ms 34832 KB Output is correct
57 Correct 860 ms 35436 KB Output is correct
58 Correct 698 ms 35692 KB Output is correct
59 Correct 595 ms 35180 KB Output is correct
60 Correct 840 ms 35308 KB Output is correct
61 Correct 112 ms 12488 KB Output is correct
62 Correct 244 ms 16492 KB Output is correct
63 Correct 484 ms 35436 KB Output is correct
64 Correct 596 ms 35428 KB Output is correct
65 Correct 789 ms 35824 KB Output is correct
66 Correct 897 ms 36076 KB Output is correct
67 Correct 476 ms 29804 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 2 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 2 ms 876 KB Output is correct
19 Correct 3 ms 876 KB Output is correct
20 Correct 3 ms 876 KB Output is correct
21 Correct 2 ms 620 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 876 KB Output is correct
24 Correct 3 ms 876 KB Output is correct
25 Correct 3 ms 876 KB Output is correct
26 Correct 3 ms 876 KB Output is correct
27 Correct 2 ms 876 KB Output is correct
28 Correct 2 ms 876 KB Output is correct
29 Correct 3 ms 876 KB Output is correct
30 Correct 2 ms 876 KB Output is correct
31 Correct 1177 ms 36464 KB Output is correct
32 Correct 423 ms 22636 KB Output is correct
33 Correct 971 ms 36096 KB Output is correct
34 Correct 1172 ms 36332 KB Output is correct
35 Correct 1090 ms 36348 KB Output is correct
36 Correct 899 ms 36236 KB Output is correct
37 Correct 722 ms 35444 KB Output is correct
38 Correct 590 ms 35200 KB Output is correct
39 Correct 526 ms 35076 KB Output is correct
40 Correct 519 ms 34996 KB Output is correct
41 Correct 899 ms 35948 KB Output is correct
42 Correct 919 ms 36084 KB Output is correct
43 Correct 156 ms 12488 KB Output is correct
44 Correct 900 ms 36076 KB Output is correct
45 Correct 924 ms 35948 KB Output is correct
46 Correct 941 ms 35692 KB Output is correct
47 Correct 432 ms 34412 KB Output is correct
48 Correct 453 ms 34028 KB Output is correct
49 Correct 493 ms 34668 KB Output is correct
50 Correct 523 ms 35184 KB Output is correct
51 Correct 539 ms 34796 KB Output is correct
52 Correct 2629 ms 133632 KB Output is correct
53 Correct 2668 ms 135416 KB Output is correct
54 Correct 938 ms 80500 KB Output is correct
55 Correct 2301 ms 132292 KB Output is correct
56 Correct 2204 ms 132048 KB Output is correct
57 Correct 2529 ms 134948 KB Output is correct
58 Correct 852 ms 80648 KB Output is correct
59 Correct 1846 ms 131944 KB Output is correct
60 Correct 2562 ms 134872 KB Output is correct
61 Correct 2789 ms 135980 KB Output is correct
62 Correct 1578 ms 135184 KB Output is correct
63 Correct 1820 ms 135640 KB Output is correct
64 Execution timed out 5071 ms 194368 KB Time limit exceeded
65 Halted 0 ms 0 KB -