Submission #53309

#	Time	Username	Problem	Language	Result	Execution time	Memory
53309		SpaimaCarpatilor	Adriatic (CEOI13_adriatic)	C++17	60 / 100	2062 ms	125708 KiB

adriatic

#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 (stderr)

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]);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20