oj.uz

Submission #666488

# Submission time Handle Problem Language Result Execution time Memory
666488 2022-11-28T17:28:00 Z rainboy Bodyguard (JOI21_bodyguard) C
100 / 100
 4621 ms 468084 KB 
#include <stdio.h>

#define M	2800
#define N	(M * 3 / 2)
#define Q	3000000

long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

long long *uu;

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)
			if (uu[ii[j]] == uu[i_])
				j++;
			else if (uu[ii[j]] < uu[i_]) {
				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 compress(long long *xx, long long *xx_, int n) {
	static int ii[M * 2];
	int n_, i;

	for (i = 0; i < n; i++)
		ii[i] = i;
	uu = xx, sort(ii, 0, n);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (i + 1 < n && xx[ii[i + 1]] == xx[ii[i]])
			xx[ii[i]] = n_;
		else
			xx_[n_] = xx[ii[i]], xx[ii[i]] = n_++;
	return n_;
}

long long xx1[M * 2], yy1[M * 2]; int cnt;

long double cross(long long x0, long long y0, long long x1, long long y1, long long x2, long long y2) {
	return (long double) (x1 - x0) * (y2 - y0) - (long double) (x2 - x0) * (y1 - y0);
}

void add(long long x, long long y) {
	if (cnt && xx1[cnt - 1] == x) {
		if (yy1[cnt - 1] >= y)
			return;
		cnt--;
	}
	while (cnt >= 2 && cross(xx1[cnt - 2], yy1[cnt - 2], xx1[cnt - 1], yy1[cnt - 1], x, y) >= 0)
		cnt--;
	xx1[cnt] = x, yy1[cnt] = y, cnt++;
}

long long query(long long y) {
	int lower = -1, upper = cnt - 1;

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

		if (xx1[h] + yy1[h] * y < xx1[h + 1] + yy1[h + 1] * y)
			lower = h;
		else
			upper = h;
	}
	return xx1[upper] + yy1[upper] * y;
}

int main() {
	static long long xx[M * 2], xx_[M * 2], yy[M * 2], yy_[M * 2], dp[N * N], aa[N * N], bb[N * N], xx0[Q], yy0[Q], ans[Q];
	static int cc[M], hh[Q];
	int nx, ny, m, q, h, h_, hl, hr, i, j;

	scanf("%d%d", &m, &q);
	for (h = 0; h < m; h++) {
		long long t, a, b;

		scanf("%lld%lld%lld%d", &t, &a, &b, &cc[h]), cc[h] /= 2;
		if (a < b) {
			xx[h << 1 | 0] = t - a, yy[h << 1 | 0] = t + a;
			xx[h << 1 | 1] = t - a, yy[h << 1 | 1] = t + b * 2 - a;
		} else {
			xx[h << 1 | 0] = t - a, yy[h << 1 | 0] = t + a;
			xx[h << 1 | 1] = t + a - b * 2, yy[h << 1 | 1] = t + a;
		}
	}
	nx = compress(xx, xx_, m * 2);
	ny = compress(yy, yy_, m * 2);
	for (h = 0; h < m; h++)
		if (xx[h << 1 | 0] == xx[h << 1 | 1]) {
			i = xx[h << 1 | 0];
			for (j = yy[h << 1 | 0]; j < yy[h << 1 | 1]; j++)
				aa[i * ny + j] = max(aa[i * ny + j], cc[h]);
		} else {
			j = yy[h << 1 | 0];
			for (i = xx[h << 1 | 0]; i < xx[h << 1 | 1]; i++)
				bb[i * ny + j] = max(bb[i * ny + j], cc[h]);
		}
	for (i = nx - 1; i >= 0; i--)
		for (j = ny - 1; j >= 0; j--) {
			dp[i * ny + j] = 0;
			if (j + 1 < ny)
				dp[i * ny + j] = max(dp[i * ny + j], dp[i * ny + (j + 1)] + (yy_[j + 1] - yy_[j]) * aa[i * ny + j]);
			if (i + 1 < nx)
				dp[i * ny + j] = max(dp[i * ny + j], dp[(i + 1) * ny + j] + (xx_[i + 1] - xx_[i]) * bb[i * ny + j]);
		}
	for (h = 0; h < q; h++) {
		int u, v, x, y;

		scanf("%d%d", &u, &v), x = u - v, y = u + v;
		xx0[h] = x, yy0[h] = y;
	}
	for (h = 0; h < q; h++)
		hh[h] = h;
	uu = xx0, sort(hh, 0, q);
	for (i = -1, hl = 0, hr = 0; i + 1 < nx; i++) {
		if (i == -1)
			hl = 0;
		else
			while (hl < q && xx0[hh[hl]] <= xx_[i])
				hl++;
		while (hr < q && xx0[hh[hr]] <= xx_[i + 1])
			hr++;
		uu = yy0, sort(hh, hl, hr);
		cnt = 0;
		for (h = hr - 1, j = ny - 1; h >= hl; h--) {
			h_ = hh[h];
			while (j >= 0 && yy0[h_] <= yy_[j])
				add(dp[(i + 1) * ny + j], i == -1 ? 0 : bb[i * ny + j]), j--;
			ans[h_] = max(ans[h_], query(xx_[i + 1] - xx0[h_]));
		}
	}
	uu = yy0, sort(hh, 0, q);
	for (j = -1, hl = 0, hr = 0; j + 1 < ny; j++) {
		if (j == -1)
			hl = 0;
		else
			while (hl < q && yy0[hh[hl]] <= yy_[j])
				hl++;
		while (hr < q && yy0[hh[hr]] <= yy_[j + 1])
			hr++;
		uu = xx0, sort(hh, hl, hr);
		cnt = 0;
		for (h = hr - 1, i = nx - 1; h >= hl; h--) {
			h_ = hh[h];
			while (i >= 0 && xx0[h_] <= xx_[i])
				add(dp[i * ny + (j + 1)], j == -1 ? 0 : aa[i * ny + j]), i--;
			ans[h_] = max(ans[h_], query(yy_[j + 1] - yy0[h_]));
		}
	}
	for (h = 0; h < q; h++)
		printf("%lld\n", ans[h]);
	return 0;
}

Compilation message

bodyguard.c: In function 'main':
bodyguard.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d", &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
bodyguard.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%lld%lld%lld%d", &t, &a, &b, &cc[h]), cc[h] /= 2;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.c:126:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   scanf("%d%d", &u, &v), x = u - v, y = u + v;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3163 ms 288808 KB Output is correct
2 Correct 3102 ms 294880 KB Output is correct
3 Correct 2774 ms 183436 KB Output is correct
4 Correct 2377 ms 133540 KB Output is correct
5 Correct 3382 ms 371808 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 283140 KB Output is correct
2 Correct 337 ms 282792 KB Output is correct
3 Correct 299 ms 272664 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 336 ms 222236 KB Output is correct
6 Correct 265 ms 192160 KB Output is correct
7 Correct 332 ms 222440 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 283140 KB Output is correct
2 Correct 337 ms 282792 KB Output is correct
3 Correct 299 ms 272664 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 336 ms 222236 KB Output is correct
6 Correct 265 ms 192160 KB Output is correct
7 Correct 332 ms 222440 KB Output is correct
8 Correct 564 ms 283856 KB Output is correct
9 Correct 521 ms 282000 KB Output is correct
10 Correct 385 ms 270692 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 401 ms 222364 KB Output is correct
13 Correct 327 ms 192188 KB Output is correct
14 Correct 292 ms 222332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 283140 KB Output is correct
2 Correct 337 ms 282792 KB Output is correct
3 Correct 299 ms 272664 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 336 ms 222236 KB Output is correct
6 Correct 265 ms 192160 KB Output is correct
7 Correct 332 ms 222440 KB Output is correct
8 Correct 564 ms 283856 KB Output is correct
9 Correct 521 ms 282000 KB Output is correct
10 Correct 385 ms 270692 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 401 ms 222364 KB Output is correct
13 Correct 327 ms 192188 KB Output is correct
14 Correct 292 ms 222332 KB Output is correct
15 Correct 760 ms 286484 KB Output is correct
16 Correct 764 ms 286488 KB Output is correct
17 Correct 512 ms 274284 KB Output is correct
18 Correct 28 ms 2764 KB Output is correct
19 Correct 397 ms 224376 KB Output is correct
20 Correct 390 ms 194304 KB Output is correct
21 Correct 312 ms 224408 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3163 ms 288808 KB Output is correct
2 Correct 3102 ms 294880 KB Output is correct
3 Correct 2774 ms 183436 KB Output is correct
4 Correct 2377 ms 133540 KB Output is correct
5 Correct 3382 ms 371808 KB Output is correct
6 Correct 315 ms 283140 KB Output is correct
7 Correct 337 ms 282792 KB Output is correct
8 Correct 299 ms 272664 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 336 ms 222236 KB Output is correct
11 Correct 265 ms 192160 KB Output is correct
12 Correct 332 ms 222440 KB Output is correct
13 Correct 564 ms 283856 KB Output is correct
14 Correct 521 ms 282000 KB Output is correct
15 Correct 385 ms 270692 KB Output is correct
16 Correct 4 ms 852 KB Output is correct
17 Correct 401 ms 222364 KB Output is correct
18 Correct 327 ms 192188 KB Output is correct
19 Correct 292 ms 222332 KB Output is correct
20 Correct 760 ms 286484 KB Output is correct
21 Correct 764 ms 286488 KB Output is correct
22 Correct 512 ms 274284 KB Output is correct
23 Correct 28 ms 2764 KB Output is correct
24 Correct 397 ms 224376 KB Output is correct
25 Correct 390 ms 194304 KB Output is correct
26 Correct 312 ms 224408 KB Output is correct
27 Correct 4589 ms 467180 KB Output is correct
28 Correct 4465 ms 468084 KB Output is correct
29 Correct 4621 ms 450484 KB Output is correct
30 Correct 3263 ms 158140 KB Output is correct
31 Correct 2291 ms 326556 KB Output is correct
32 Correct 3906 ms 355216 KB Output is correct
33 Correct 3883 ms 376236 KB Output is correct