# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
164379 | frodakcin | Adriatic (CEOI13_adriatic) | C++11 | 356 ms | 206484 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
using ll = long long;
const int MN = 2.5e5 + 100;
const int MX = 2.5e3 + 10;
int N;
int nx[MX][MX], ny[MX][MX];
ll v[MX][MX];
ll f[MN];
struct ISL
{
public:
int x, y;
void in(void) {scanf("%d%d", &x, &y);}
void flip(void) {x = MX - x - 1, y = MX - y - 1;}
};
ISL a[MN];
void solve(void)
{
memset(nx, -1, sizeof(nx));
memset(ny, -1, sizeof(ny));
memset(v, 0, sizeof(v));
for(int i = 0, x, y;i < N;++i)
x = a[i].x, y = a[i].y,
v[x][y] = 1LL,
nx[x+1][y+1] = x, ny[x-1][y-1] = y;
for(int i = 0;i < MX;++i)
for(int j = 0;j < MX;++j)
{
if(i && ~nx[i-1][j] && (nx[i-1][j] < nx[i][j] || !~nx[i][j]))
nx[i][j] = nx[i-1][j];
if(j && ~nx[i][j-1] && (nx[i][j-1] < nx[i][j] || !~nx[i][j]))
nx[i][j] = nx[i][j-1];
}
for(int i = MX;i >= 0;--i)
for(int j = MX;j >= 0;--j)
{
if(i<MX && ny[i+1][j] > ny[i][j])
ny[i][j] = ny[i+1][j];
if(j<MX && ny[i][j+1] > ny[i][j])
ny[i][j] = ny[i][j+1];
}
for(int i = 0;i < MX;++i)
for(int j = 0;j < MX;++j)
{
if(!~nx[i][j] || nx[i][j] > i) nx[i][j] = i;
if(ny[i][j] < j) ny[i][j] = j;
}
for(int i = 0;i < MX;++i)
{
for(int j = MX-2;j >= 0;--j)
v[i][j] += v[i][j+1];
if(i)
for(int j = 0;j < MX;++j)
v[i][j] += v[i-1][j];
}
for(int i = 0;i < MX;++i)
for(int j = MX;j >= 0;--j)
if(v[i][j])
v[i][j] += v[nx[i][j]][ny[i][j]];
for(int i = 0;i < N;++i)
f[i] += v[a[i].x][a[i].y] - 1;
}
int main(void)
{
scanf("%d", &N);
for(int i = 0;i < N;++i)
a[i].in();
solve();
for(int i = 0;i < N;++i)
a[i].flip();
solve();
for(int i = 0;i < N;++i)
printf("%lld\n", f[i]+N-1);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |