Submission #555949

#	Time	Username	Problem	Language	Result	Execution time	Memory
555949		rainboy	방벽 (JOI15_walls)	C11	100 / 100	271 ms	19276 KiB

walls

#include <stdio.h>
#include <string.h>
 
#define N	200000
#define M	200000
 
int abs_(int a) { return a > 0 ? a : -a; }
long long max(long long a, long long b) { return a > b ? a : b; }
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
int ll[N], rr[N], dd[N];
 
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 (dd[ii[j]] == dd[i_])
				j++;
			else if (dd[ii[j]] < dd[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 dd_[M], iq[M + 1], pq[M], cnt;
 
int lt(int i, int j) { return dd_[i] < dd_[j]; }
 
int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
 
void pq_up(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_dn(int i) {
	int p, q, j;
 
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}
 
void pq_add(int i) {
	pq[i] = ++cnt, pq_up(i);
}
 
void pq_remove(int i) {
	int j = iq[cnt--];
 
	if (j != i)
		pq[j] = pq[i], pq_up(j), pq_dn(j);
	pq[i] = 0;
}
 
int pq_first() {
	return iq[1];
}
 
int main() {
	static int ii[N], xx[M], qu[M], pp[M], qq[M];
	static long long ans[N];
	int n, m, r, h, i, i_, j, j1, j2, k, p, q, cnt_, tmp;
	long long sum;
 
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &ll[i], &rr[i]);
		if (ll[i] > rr[i])
			tmp = ll[i], ll[i] = rr[i], rr[i] = tmp;
		dd[i] = rr[i] - ll[i];
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (j = 0; j < m; j++)
		scanf("%d", &xx[j]);
	for (r = 0; r < 2; r++) {
		cnt_ = 0;
		for (j = 0; j < m; j++) {
			if (cnt_ && (xx[qu[cnt_ - 1]] < xx[j]) == (cnt_ % 2 == 1))
				cnt_--;
			qu[cnt_++] = j;
		}
		memset(pp, -1, m * sizeof *pp), memset(qq, -1, m * sizeof *qq);
		memset(pq, 0, m * sizeof *pq), cnt = 0;
		sum = xx[qu[0]], k = 1;
		for (h = 0; h + 1 < cnt_; h++) {
			j1 = qu[h], j2 = qu[h + 1];
			qq[j1] = j2, pp[j2] = j1, dd_[j1] = abs_(xx[j1] - xx[j2]), pq_add(j1);
			sum += dd_[j1], k++;
		}
		for (i = 0; i < n; i++) {
			i_ = ii[i];
			while (cnt && dd_[j1 = pq_first()] <= dd[i_]) {
				j2 = qq[j1], p = pp[j1], q = qq[j2];
				sum -= dd_[j1], k--, pq_remove(j1);
				if (q == -1)
					qq[j1] = -1;
				else {
					sum -= dd_[j2], k--, pq_remove(j2);
					pp[q] = p;
					if (p != -1) {
						sum -= dd_[p];
						qq[p] = q, dd_[p] = abs_(xx[p] - xx[q]), pq_up(p), pq_dn(p);
						sum += dd_[p];
					} else
						sum += xx[q] - xx[j1];
				}
			}
			ans[i_] = max(ans[i_], sum - (long long) dd[i_] * k - ll[i_]);
		}
		for (i = 0; i < n; i++)
			tmp = -ll[i], ll[i] = -rr[i], rr[i] = tmp;
		for (j = 0; j < m; j++)
			xx[j] = -xx[j];
	}
	for (i = 0; i < n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

walls.c: In function 'main':
walls.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
walls.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", &ll[i], &rr[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.c:93:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d", &xx[j]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 45 / 45