#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
#define N_ 2000
#define Q 500000
#define X 2000
#define T 1000
#define INF 0x7fffffff
long long abs_(long long a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], n;
int tt[Q]; long long ans[Q]; int q;
int compare_x(int i, int j) {
return xx[i] - xx[j];
}
int tt_[N];
int compare_t_(int i, int j) {
return tt_[i] != tt_[j] ? (tt_[i] < tt_[j] ? -1 : 1) : 0;
}
int (*compare)(int, int);
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) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
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;
}
}
void solve2() {
static int dd[X * 2 + 1][X * 2 + 1], nn[T + 1];
int h, i, x, y;
for (x = 0; x <= X * 2; x++)
for (y = 0; y <= X * 2; y++)
dd[x][y] = T + 1;
for (i = 0; i < n; i++)
dd[X + xx[i]][X + yy[i]] = 0;
for (x = 0; x <= X * 2; x++) {
for (y = 1; y <= X * 2; y++)
dd[x][y] = min(dd[x][y], dd[x][y - 1] + 1);
for (y = X * 2 - 1; y >= 0; y--)
dd[x][y] = min(dd[x][y], dd[x][y + 1] + 1);
}
for (y = 0; y <= X * 2; y++) {
for (x = 1; x <= X * 2; x++)
dd[x][y] = min(dd[x][y], dd[x - 1][y] + 1);
for (x = X * 2 - 1; x >= 0; x--)
dd[x][y] = min(dd[x][y], dd[x + 1][y] + 1);
}
memset(nn, 0, (T + 1) * sizeof *nn);
for (x = 0; x <= X * 2; x++)
for (y = 0; y <= X * 2; y++)
if (dd[x][y] <= T)
nn[dd[x][y]]++;
for (h = 0; h < q; h++)
ans[h] = nn[tt[h]];
}
void solve4() {
static int ii[N];
int h, i, i_, a;
long long b, t;
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_x, sort(ii, 0, n);
for (i = 0; i + 1 < n; i++) {
tt_[i] = xx[ii[i + 1]] - xx[ii[i]];
ii[i] = i;
}
compare = compare_t_, sort(ii, 0, n - 1);
i = 0, a = n * 4, b = 0;
for (h = 0; h < q; h++) {
t = tt[h];
if (t == 0) {
ans[h] = n;
continue;
}
while (i < n - 1 && tt_[i_ = ii[i]] < t) {
a -= 4, b += (long long) tt_[i_] * 2;
i++;
}
ans[h] = 0;
while (i < n - 1 && tt_[i_ = ii[i]] == t) {
ans[h] += t - 1;
a -= 4, b += (long long) tt_[i_] * 2;
i++;
}
ans[h] += (long long) a * t + b;
}
}
long long uu[N], vv[N];
int aa[Q + 1]; long long bb[Q + 1];
void add(int t, int a, long long b) {
int lower = -1, upper = q;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (tt[h] >= t)
upper = h;
else
lower = h;
}
aa[upper] += a, bb[upper] += b;
}
void solve6() {
static int jj[N];
int cnt, h, i, j, r, t, tmp;
long long u, u_, ul, ur;
for (i = 0; i < n; i++)
uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
memset(aa, 0, (q + 1) * sizeof *aa), memset(bb, 0, (q + 1) * sizeof *bb);
for (r = 0; r < 4; r++) {
for (i = 0; i < n; i++) {
cnt = 0;
for (j = 0; j < n; j++)
if (j != i) {
if (vv[i] > vv[j] || vv[i] == vv[j] && i < j)
continue;
tt_[j] = (max(abs_(uu[i] - uu[j]), abs_(vv[i] - vv[j])) + (i < j ? 2 : 1)) / 2;
jj[cnt++] = j;
}
compare = compare_t_, sort(jj, 0, cnt);
add(0, 1, 0);
u = uu[i], ul = -INF, ur = INF, t = INF;
for (h = 0; h <= cnt; h++) {
if (h == cnt) {
t = ul != -INF && ur != INF ? (ur - ul) / 2 + 1 : INF;
break;
}
j = jj[h], t = tt_[j];
if (ul != -INF && ur != INF && ul + t > ur - t) {
t = (ur - ul) / 2 + 1;
break;
}
if (uu[j] < u) {
u_ = uu[j] + (i < j ? 0 : 1);
if (ul == -INF)
ul = u_, add(t, -1, (u - u_) / 2);
else if (ul < u_)
add(t, 0, (u - u_) / 2 - (u - ul) / 2), ul = u_;
} else {
u_ = uu[j] - (i < j ? 0 : 1);
if (ur == INF)
ur = u_, add(t, -1, (u_ - u + 2) / 2);
else if (ur > u_)
add(t, 0, (u_ - u + 2) / 2 - (ur - u + 2) / 2), ur = u_;
}
if (ul != -INF && ur != INF && ul + t > ur - t)
break;
}
if (t != INF)
add(t, 1, -((u - ul) / 2 + (ur - u + 2) / 2));
}
for (i = 0; i < n; i++) {
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
}
}
for (h = 1; h < q; h++)
aa[h] += aa[h - 1], bb[h] += bb[h - 1];
for (h = 0; h < q; h++)
ans[h] = tt[h] == 0 ? n : (long long) aa[h] * tt[h] + bb[h];
}
void test() {
static long long ans_[Q];
int h;
solve2(), memcpy(ans_, ans, q * sizeof *ans), solve6();
for (h = 0; h < q; h++)
if (ans[h] != ans_[h]) {
printf("wrong answer on query %d: expected %lld, found %lld\n", h + 1, ans_[h], ans[h]);
exit(0);
}
}
void stress() {
int t, h, i, j;
for (t = 1; t <= T; t++) {
printf("running on test %d...\n", t);
generate:
n = 10, q = T + 1;
for (i = 0; i < n; i++)
xx[i] = rand_() % 2001 - 1000, yy[i] = rand_() % 2001 - 1000;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (xx[j] == xx[i] && yy[j] == yy[i])
goto generate;
for (h = 0; h < q; h++)
tt[h] = h;
test();
}
printf("AC\n");
}
int main() {
int h, i, subtask;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
for (h = 0; h < q; h++)
scanf("%d", &tt[h]);
#if 1
stress();
#endif
if (n <= N_)
subtask = 6;
else {
subtask = 4;
for (i = 0; i < n; i++)
if (xx[i] != yy[i]) {
subtask = 2;
break;
}
}
if (subtask == 2)
solve2();
else if (subtask == 4)
solve4();
else if (subtask == 6)
solve6();
for (h = 0; h < q; h++)
printf("%lld\n", ans[h]);
return 0;
}
Compilation message
cell.c: In function 'solve6':
cell.c:153:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
153 | if (vv[i] > vv[j] || vv[i] == vv[j] && i < j)
| ~~~~~~~~~~~~~~~^~~~~~~~
cell.c: In function 'main':
cell.c:236:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
236 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
cell.c:238:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
238 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:240:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
240 | scanf("%d", &tt[h]);
| ^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8093 ms |
74832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8093 ms |
74832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8022 ms |
76964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8022 ms |
76964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8047 ms |
74836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8047 ms |
74836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8093 ms |
74832 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
