Submission #666488

#	Time	Username	Problem	Language	Result	Execution time	Memory
666488		rainboy	Bodyguard (JOI21_bodyguard)	C11	100 / 100	4621 ms	468084 KiB

bodyguard

#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 (stderr)

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52