| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53117 |
2018-06-28T12:32:17 Z |
Costin Andrei Oncescu(#1297) |
Adriatic (CEOI13_adriatic) |
C++11 |
|
2000 ms |
128852 KB |
#include<bits/stdc++.h>
using namespace std;
int M, source, ans[250009], 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 getCount (int a, int b, int c, int d)
{
if (a < x[source] && x[source] < c && b < y[source] && y[source] < d)
return 1 + sum (1, 1, a, b) + sum (c, d, N, N);///they don't intersect at all
int ans = M;///then subtract those that are not inside
ans -= sum (1, b + 1, c - 1, N);
ans -= sum (a + 1, 1, N, d - 1);
return ans;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
read ();
for (source = 1; source <= M; source ++)
{
int A = x[source] - 1, B = y[source] - 1, C = x[source] + 1, D = y[source] + 1;
int cnt = getCount (A, B, C, D);
ans[source] = cnt - 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 = max (nA, maxX[C][D] - 1), nB = max (nB, maxY[C][D] - 1);
nC = min (nC, minX[A][B] + 1), nD = min (nD, minY[A][B] + 1);
int nCnt = getCount (nA, nB, nC, nD);
A = nA, B = nB, C = nC, D = nD;
ans[source] += d * (nCnt - cnt);
cnt = nCnt;
//printf ("%d %d %d %d %d\n\n", A, B, C, D, cnt);
}
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 |
157 ms |
123000 KB |
Output is correct |
| 2 |
Correct |
144 ms |
123000 KB |
Output is correct |
| 3 |
Correct |
145 ms |
123032 KB |
Output is correct |
| 4 |
Correct |
140 ms |
123092 KB |
Output is correct |
| 5 |
Correct |
197 ms |
123296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
123296 KB |
Output is correct |
| 2 |
Correct |
150 ms |
123352 KB |
Output is correct |
| 3 |
Correct |
155 ms |
123352 KB |
Output is correct |
| 4 |
Correct |
149 ms |
123352 KB |
Output is correct |
| 5 |
Correct |
171 ms |
123352 KB |
Output is correct |
| 6 |
Correct |
215 ms |
123352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
123460 KB |
Output is correct |
| 2 |
Correct |
148 ms |
123460 KB |
Output is correct |
| 3 |
Correct |
169 ms |
123460 KB |
Output is correct |
| 4 |
Correct |
147 ms |
123460 KB |
Output is correct |
| 5 |
Correct |
148 ms |
123460 KB |
Output is correct |
| 6 |
Correct |
960 ms |
123696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1578 ms |
123952 KB |
Output is correct |
| 2 |
Correct |
196 ms |
123984 KB |
Output is correct |
| 3 |
Correct |
231 ms |
124172 KB |
Output is correct |
| 4 |
Correct |
166 ms |
124428 KB |
Output is correct |
| 5 |
Correct |
158 ms |
124648 KB |
Output is correct |
| 6 |
Execution timed out |
2069 ms |
125020 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
128852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
