oj.uz

답안 #53117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53117 2018-06-28T12:32:17 Z Costin Andrei Oncescu(#1297) 섬 항해 (CEOI13_adriatic) C++11
60 / 100
 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]);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2087 ms 128852 KB Time limit exceeded
2 Halted 0 ms 0 KB -