#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]), 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);
if (p != -1) {
sum -= dd_[p];
qq[p] = q, pp[q] = p, dd_[p] = abs_(xx[q] - xx[p]), pq_up(p), pq_dn(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]), dd[i] = rr[i] - ll[i];
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.c:90:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d", &xx[j]);
| ^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
19 ms |
2820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
