#include<bits/stdc++.h>
using namespace std;
int M, source, x[250009], y[250009];
const int N = 2500;
int s[N + 5][N + 5], minX[N + 5][N + 5], maxX[N + 5][N + 5], minY[N + 5][N + 5], maxY[N + 5][N + 5];
void read ()
{
scanf ("%d", &M);
for (int i=0; i<=N + 1; i++)
for (int j=0; j<=N + 1; j++)
minX[i][j] = minY[i][j] = N + 1,
maxX[i][j] = maxY[i][j] = 0;
for (int i=1; i<=M; i++)
scanf ("%d %d", &x[i], &y[i]), s[x[i]][y[i]] ++,
minX[x[i]][y[i]] = min (minX[x[i]][y[i]], x[i]),
maxX[x[i]][y[i]] = max (maxX[x[i]][y[i]], x[i]),
minY[x[i]][y[i]] = min (minY[x[i]][y[i]], y[i]),
maxY[x[i]][y[i]] = max (maxY[x[i]][y[i]], y[i]);
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1],
minX[i][j] = min ({minX[i][j], minX[i - 1][j], minX[i][j - 1]}),
minY[i][j] = min ({minY[i][j], minY[i - 1][j], minY[i][j - 1]});
for (int i=N; i>=1; i--)
for (int j=N; j>=1; j--)
maxX[i][j] = max ({maxX[i][j], maxX[i + 1][j], maxX[i][j + 1]}),
maxY[i][j] = max ({maxY[i][j], maxY[i + 1][j], maxY[i][j + 1]});
}
int sum (int a1, int b1, int a2, int b2)
{
return s[a2][b2] - s[a1 - 1][b2] - s[a2][b1 - 1] + s[a1 - 1][b1 - 1];
}
int upRightC[N + 5][N + 5];
long long upRightS[N + 5][N + 5];
void prepareUpRight ()
{
for (int i=1; i<=N; i++)
for (int j=N; j>=1; j--)
{
int currCnt = sum (1, j, i, N);
int x = min (i, minX[i][j - 1]), y = max (j, maxY[i + 1][j]);
if (currCnt == 0 || (x == i && y == j))
upRightS[i][j] = currCnt, upRightC[i][j] = 0;
else
{
upRightS[i][j] = upRightS[x][y] + currCnt;
upRightC[i][j] = upRightC[x][y] + 1;
}
}
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
if (sum (1, j, i, N) == 1)
upRightS[i][j] = 1, upRightC[i][j] = 0;
}
int downLeftC[N + 5][N + 5];
long long downLeftS[N + 5][N + 5];
void prepareDownLeft ()
{
for (int i=N; i>=1; i--)
for (int j=1; j<=N; j++)
{
int currCnt = sum (i, 1, N, j);
int x = max (i, maxX[i][j + 1]), y = min (j, minY[i - 1][j]);
if (currCnt == 0 || (x == i && y == j))
downLeftS[i][j] = currCnt, downLeftC[i][j] = 0;
else
{
downLeftS[i][j] = downLeftS[x][y] + currCnt;
downLeftC[i][j] = downLeftC[x][y] + 1;
}
}
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
if (sum (i, 1, N, j) == 1)
downLeftS[i][j] = 1, downLeftC[i][j] = 0;
}
void prepare ()
{
prepareUpRight ();
prepareDownLeft ();
}
int getCount (int a, int b, int c, int d)
{
int ans = M;///then subtract those that are not inside
ans -= sum (1, b, a, N);
ans -= sum (c, 1, N, d);
ans += (x[source] <= a && y[source] >= b);
ans += (x[source] >= c && y[source] <= d);
return ans;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
read ();
if (M == 1)
{
printf ("0\n");
return 0;
}
prepare ();
for (source = 1; source <= M; source ++)
{
// int A = x[source], B = y[source], C = x[source], D = y[source];
int px = x[source], py = y[source];
int maxD = max (upRightC[px][py], downLeftC[px][py]);
long long sumCnt = upRightS[px][py] + downLeftS[px][py] - 2;
sumCnt = 1LL * maxD * M - sumCnt, sumCnt ++, maxD ++;
/* for (int d=2; cnt < M; d++)
{
//printf ("%d %d %d %d %d ->\n", A, B, C, D, cnt);
int nA = A, nB = B, nC = C, nD = D;
nA = min (nA, minX[A][B - 1]), nB = max (nB, maxY[A + 1][B]);
nC = max (nC, maxX[C][D + 1]), nD = min (nD, minY[C - 1][D]);
int nCnt = getCount (nA, nB, nC, nD);
A = nA, B = nB, C = nC, D = nD;
maxD = d, sumCnt += cnt;
cnt = nCnt;
//printf ("%d %d %d %d %d\n\n", A, B, C, D, cnt);
}*/
printf ("%lld\n", 1LL * maxD * M - sumCnt);
// printf ("%d\n", ans[source]);
}
return 0;
}
Compilation message
adriatic.cpp: In function 'void read()':
adriatic.cpp:11:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &M);
~~~~~~^~~~~~~~~~
adriatic.cpp:20:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &x[i], &y[i]), s[x[i]][y[i]] ++,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
minX[x[i]][y[i]] = min (minX[x[i]][y[i]], x[i]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maxX[x[i]][y[i]] = max (maxX[x[i]][y[i]], x[i]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
minY[x[i]][y[i]] = min (minY[x[i]][y[i]], y[i]),
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
maxY[x[i]][y[i]] = max (maxY[x[i]][y[i]], y[i]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
270044 KB |
Output is correct |
| 2 |
Correct |
314 ms |
270148 KB |
Output is correct |
| 3 |
Correct |
443 ms |
270148 KB |
Output is correct |
| 4 |
Correct |
310 ms |
270248 KB |
Output is correct |
| 5 |
Correct |
314 ms |
270272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
322 ms |
270376 KB |
Output is correct |
| 2 |
Correct |
282 ms |
270376 KB |
Output is correct |
| 3 |
Correct |
310 ms |
270376 KB |
Output is correct |
| 4 |
Correct |
308 ms |
270376 KB |
Output is correct |
| 5 |
Correct |
365 ms |
270492 KB |
Output is correct |
| 6 |
Correct |
319 ms |
270492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
270492 KB |
Output is correct |
| 2 |
Correct |
289 ms |
270492 KB |
Output is correct |
| 3 |
Correct |
324 ms |
270492 KB |
Output is correct |
| 4 |
Correct |
272 ms |
270492 KB |
Output is correct |
| 5 |
Correct |
288 ms |
270492 KB |
Output is correct |
| 6 |
Correct |
410 ms |
270496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
404 ms |
270884 KB |
Output is correct |
| 2 |
Correct |
302 ms |
270884 KB |
Output is correct |
| 3 |
Correct |
343 ms |
270884 KB |
Output is correct |
| 4 |
Correct |
283 ms |
270884 KB |
Output is correct |
| 5 |
Correct |
309 ms |
270884 KB |
Output is correct |
| 6 |
Correct |
409 ms |
270884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
546 ms |
274376 KB |
Output is correct |
| 2 |
Correct |
471 ms |
274376 KB |
Output is correct |
| 3 |
Correct |
515 ms |
274376 KB |
Output is correct |
| 4 |
Correct |
448 ms |
274376 KB |
Output is correct |
| 5 |
Correct |
430 ms |
274376 KB |
Output is correct |
| 6 |
Correct |
553 ms |
274488 KB |
Output is correct |
| 7 |
Correct |
575 ms |
274488 KB |
Output is correct |
