#include <stdio.h>
#include <string.h>
#define N 250000
#define N_ 5000
#define Y 2500
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], yy[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) {
int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[i_] - yy[ii[j]];
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;
}
}
int ft[Y + 1];
void update(int i) {
while (i <= Y) {
ft[i]++;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int main() {
static int ii[N], ii1[N_], ii2[N_], ll1[N], rr1[N], ll2[N], rr2[N], ans[N], dp[N_][N_];
int n, n1, n2, i, j, tmp;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
ii[i] = i;
}
sort(ii, 0, n);
for (i = 0; i < n; i++)
ans[i] = (n - 1) * 2;
for (i = 0; i < n; i++) {
ans[ii[i]] -= query(yy[ii[i]] - 1);
update(yy[ii[i]]);
}
memset(ft, 0, (Y + 1) * sizeof *ft);
for (i = n - 1; i >= 0; i--) {
ans[ii[i]] -= query(Y - yy[ii[i]] - 1);
update(Y - yy[ii[i]]);
}
n1 = 0;
for (i = 0; i < n; i++)
if (n1 == 0 || yy[ii1[n1 - 1]] >= yy[ii[i]])
ii1[n1++] = ii[i];
n2 = 0;
for (i = n - 1; i >= 0; i--)
if (n2 == 0 || yy[ii2[n2 - 1]] <= yy[ii[i]])
ii2[n2++] = ii[i];
for (i = 0, j = n2 - 1; i < j; i++, j--)
tmp = ii2[i], ii2[i] = ii2[j], ii2[j] = tmp;
for (i = 0; i < n; i++) {
int lower, upper;
lower = -1, upper = n1;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (yy[ii1[h]] < yy[i])
upper = h;
else
lower = h;
}
ll1[i] = upper;
lower = -1, upper = n1;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (xx[ii1[h]] < xx[i])
lower = h;
else
upper = h;
}
rr1[i] = lower;
}
for (i = 0; i < n; i++) {
int lower, upper;
lower = -1, upper = n2;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (xx[ii2[h]] > xx[i])
upper = h;
else
lower = h;
}
ll2[i] = upper;
lower = -1, upper = n2;
while (upper - lower > 1) {
int h = (lower + upper) / 2;
if (yy[ii2[h]] > yy[i])
lower = h;
else
upper = h;
}
rr2[i] = lower;
}
for (i = 0; i < n1; i++)
ll1[ii1[i]] = rr1[ii1[i]] = i;
for (i = 0; i < n2; i++)
ll2[ii2[i]] = rr2[ii2[i]] = i;
for (i = 0; i < n; i++)
if (rr1[i] + 1 < n1 && rr2[i] + 1 < n2)
dp[rr1[i] + 1][rr2[i] + 1]++;
for (i = 0; i < n1; i++)
for (j = 1; j < n2; j++)
dp[i][j] += dp[i][j - 1];
for (j = 0; j < n2; j++)
for (i = 1; i < n1; i++)
dp[i][j] += dp[i - 1][j];
for (i = 0; i < n1; i++)
for (j = 0; j < n2; j++)
dp[i][j] += dp[min(i, ll1[ii2[j]])][min(j, ll2[ii1[i]])];
for (i = 0; i < n; i++)
ans[i] += dp[ll1[i]][ll2[i]];
for (i = 0; i < n1; i++)
memset(dp[i], 0, n2 * sizeof *dp[i]);
for (i = 0; i < n; i++)
if (ll1[i] > 0 && ll2[i] > 0)
dp[ll1[i] - 1][ll2[i] - 1]++;
for (i = n1 - 1; i >= 0; i--)
for (j = n2 - 2; j >= 0; j--)
dp[i][j] += dp[i][j + 1];
for (j = n2 - 1; j >= 0; j--)
for (i = n1 - 2; i >= 0; i--)
dp[i][j] += dp[i + 1][j];
for (i = n1 - 1; i >= 0; i--)
for (j = n2 - 1; j >= 0; j--)
dp[i][j] += dp[max(i, rr1[ii2[j]])][max(j, rr2[ii1[i]])];
for (i = 0; i < n; i++)
ans[i] += dp[rr1[i]][rr2[i]];
for (i = 0; i < n; i++)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
adriatic.c: In function 'main':
adriatic.c:64:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
adriatic.c:66:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
428 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
432 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1876 KB |
Output is correct |
| 4 |
Correct |
2 ms |
432 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
7472 KB |
Output is correct |
| 2 |
Correct |
4 ms |
724 KB |
Output is correct |
| 3 |
Correct |
16 ms |
6056 KB |
Output is correct |
| 4 |
Correct |
3 ms |
692 KB |
Output is correct |
| 5 |
Correct |
3 ms |
724 KB |
Output is correct |
| 6 |
Correct |
221 ms |
32828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
682 ms |
89604 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1492 KB |
Output is correct |
| 3 |
Correct |
48 ms |
12180 KB |
Output is correct |
| 4 |
Correct |
17 ms |
1944 KB |
Output is correct |
| 5 |
Correct |
18 ms |
2084 KB |
Output is correct |
| 6 |
Correct |
226 ms |
32240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1198 ms |
108808 KB |
Output is correct |
| 2 |
Correct |
186 ms |
13004 KB |
Output is correct |
| 3 |
Correct |
256 ms |
21452 KB |
Output is correct |
| 4 |
Correct |
197 ms |
15140 KB |
Output is correct |
| 5 |
Correct |
186 ms |
13104 KB |
Output is correct |
| 6 |
Correct |
402 ms |
42644 KB |
Output is correct |
| 7 |
Correct |
512 ms |
46796 KB |
Output is correct |
