oj.uz

Submission #555949

# Submission time Handle Problem Language Result Execution time Memory
555949 2022-05-01T21:38:40 Z rainboy None (JOI15_walls) C
100 / 100
 271 ms 19276 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 76 ms 5260 KB Output is correct
3 Correct 93 ms 5832 KB Output is correct
4 Correct 80 ms 5696 KB Output is correct
5 Correct 102 ms 5688 KB Output is correct
6 Correct 68 ms 5764 KB Output is correct
7 Correct 24 ms 3412 KB Output is correct
8 Correct 25 ms 3416 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1492 KB Output is correct
2 Correct 112 ms 8156 KB Output is correct
3 Correct 105 ms 10832 KB Output is correct
4 Correct 271 ms 17604 KB Output is correct
5 Correct 205 ms 17004 KB Output is correct
6 Correct 252 ms 17596 KB Output is correct
7 Correct 201 ms 16968 KB Output is correct
8 Correct 235 ms 17604 KB Output is correct
9 Correct 106 ms 13148 KB Output is correct
10 Correct 200 ms 16728 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 76 ms 5260 KB Output is correct
3 Correct 93 ms 5832 KB Output is correct
4 Correct 80 ms 5696 KB Output is correct
5 Correct 102 ms 5688 KB Output is correct
6 Correct 68 ms 5764 KB Output is correct
7 Correct 24 ms 3412 KB Output is correct
8 Correct 25 ms 3416 KB Output is correct
9 Correct 16 ms 1492 KB Output is correct
10 Correct 112 ms 8156 KB Output is correct
11 Correct 105 ms 10832 KB Output is correct
12 Correct 271 ms 17604 KB Output is correct
13 Correct 205 ms 17004 KB Output is correct
14 Correct 252 ms 17596 KB Output is correct
15 Correct 201 ms 16968 KB Output is correct
16 Correct 235 ms 17604 KB Output is correct
17 Correct 106 ms 13148 KB Output is correct
18 Correct 200 ms 16728 KB Output is correct
19 Correct 229 ms 18680 KB Output is correct
20 Correct 261 ms 19276 KB Output is correct
21 Correct 209 ms 18636 KB Output is correct
22 Correct 254 ms 18136 KB Output is correct
23 Correct 206 ms 18476 KB Output is correct
24 Correct 257 ms 19216 KB Output is correct
25 Correct 131 ms 15472 KB Output is correct
26 Correct 126 ms 16076 KB Output is correct
27 Correct 240 ms 18700 KB Output is correct