#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 upRightS[N + 5][N + 5], upRightC[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);
if (currCnt == 0)
upRightS[i][j] = upRightC[i][j] = 0;
else
{
int x = min (i, minX[i][j - 1]), y = max (j, maxY[i + 1][j]);
upRightS[i][j] = upRightS[x][y] + currCnt;
upRightC[i][j] = upRightC[x][y] + 1;
}
}
}
int downLeftS[N + 5][N + 5], downLeftC[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);
if (currCnt == 0)
downLeftS[i][j] = downLeftC[i][j] = 0;
else
{
int x = max (i, maxX[i][j + 1]), y = min (j, minY[i - 1][j]);
downLeftS[i][j] = downLeftS[x][y] + currCnt;
downLeftC[i][j] = downLeftC[x][y] + 1;
}
}
}
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;
}
for (source = 1; source <= M; source ++)
{
int A = x[source], B = y[source], C = x[source], D = y[source], maxD = 1;
int cnt = getCount (A, B, C, D), sumCnt = 1;
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 ("%d\n", 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 |
163 ms |
123000 KB |
Output is correct |
| 2 |
Correct |
139 ms |
123112 KB |
Output is correct |
| 3 |
Correct |
142 ms |
123112 KB |
Output is correct |
| 4 |
Correct |
140 ms |
123208 KB |
Output is correct |
| 5 |
Correct |
149 ms |
123240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
123240 KB |
Output is correct |
| 2 |
Correct |
148 ms |
123268 KB |
Output is correct |
| 3 |
Correct |
149 ms |
123312 KB |
Output is correct |
| 4 |
Correct |
144 ms |
123320 KB |
Output is correct |
| 5 |
Correct |
145 ms |
123320 KB |
Output is correct |
| 6 |
Correct |
170 ms |
123320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
123320 KB |
Output is correct |
| 2 |
Correct |
159 ms |
123332 KB |
Output is correct |
| 3 |
Correct |
206 ms |
123520 KB |
Output is correct |
| 4 |
Correct |
176 ms |
123520 KB |
Output is correct |
| 5 |
Correct |
147 ms |
123520 KB |
Output is correct |
| 6 |
Correct |
665 ms |
123684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1154 ms |
123820 KB |
Output is correct |
| 2 |
Correct |
171 ms |
123820 KB |
Output is correct |
| 3 |
Correct |
210 ms |
123820 KB |
Output is correct |
| 4 |
Correct |
153 ms |
123820 KB |
Output is correct |
| 5 |
Correct |
158 ms |
123820 KB |
Output is correct |
| 6 |
Execution timed out |
2052 ms |
123820 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
125708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
