oj.uz

Submission #839757

# Submission time Handle Problem Language Result Execution time Memory
839757 2023-08-30T15:50:17 Z model_code Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 140412 KB 
// correct/BM_bigRec_N3log.cpp

#include "soccer.h"

#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int MAXN = 3202;

int N, maxi, where;
int F[MAXN][MAXN];
int bMost[MAXN];
int id[MAXN];
set<int> block;
pair<pair<int, int>, int> ans[MAXN * MAXN];
int up[MAXN][MAXN];
int down[MAXN][MAXN];
int sum[MAXN][MAXN];

bool small(int x, int y)
{
    return bMost[x] > bMost[y];
}

int biggest_stadium(int NN, std::vector<std::vector<int>> FF)
{
    N = NN;
    N += 2;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            F[i][j] = 1;
        id[i] = i;
    }

    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
            F[i][j] = FF[i - 1][j - 1];
    }

    bMost[0] = -1;
    bMost[N - 1] = -1;

    for (int j = 0; j < N; j++)
        down[N - 1][j] = N - 1;
    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 0; j < N; j++)
        {
            up[i][j] = up[i - 1][j];
            down[N - 1 - i][j] = down[N - i][j];
            if (F[i][j] == 1)
                up[i][j] = i;
            if (F[N - 1 - i][j] == 1)
                down[N - 1 - i][j] = N - 1 - i;
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            sum[i][j] = F[i][j];
            if (j != 0)
                sum[i][j] += sum[i][j - 1];
        }
    }

    for (int i = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            if (F[i][j] == 1)
                bMost[j] = i;
        }
        std::sort(id + 1, id + N - 1, small);
        block.clear();
        block.insert(0);
        block.insert(N - 1);

        for (int j = 1; j < N - 1; j++)
        {
            int pos = id[j];
            if (bMost[pos] != i)
            {
                auto it = block.lower_bound(pos);
                int b = (*it);
                it--;
                int a = (*it);
                int v = i - bMost[pos], h = b - a - 1;
                if (bMost[a] != bMost[pos] && bMost[b] != bMost[pos] && sum[i + 1][b - 1] - sum[i + 1][a] >= 1)
                {
                    ans[where++] = {{h * N + (a + 1), v * N + (bMost[pos] + 1)}, v * h};
                }
            }
            block.insert(pos);
        }
    }

    sort(ans, ans + where);

    for (int mId = 0; mId < where; mId++)
    {
        auto i = ans[mId];
        maxi = i.second;

        int h1 = i.first.first % N, h2 = i.first.first % N + i.first.first / N - 1;
        int v1 = i.first.second % N, v2 = i.first.second % N + i.first.second / N - 1;

        int last = h1 - 1, upMax = 0, downMin = N - 1;
        for (int j = h1; j <= h2 + 1; j++)
        {
            if (j == h2 + 1 || F[v1 - 1][j] == 1)
            {
                if (last + 1 < j)
                {
                    int val1 = (j - last - 1) * N + (last + 1), val2 = (downMin - upMax - 1) * N + (upMax + 1);
                    int l = 0, r = mId - 1;
                    while (l != r)
                    {
                        int half = (l + r) / 2;
                        if (ans[half].first.first < val1 || (ans[half].first.first == val1 && ans[half].first.second < val2))
                        {
                            l = half + 1;
                        }
                        else
                        {
                            r = half;
                        }
                    }
                    const auto &k = ans[l];
                    if (k.first.first != val1 || k.first.second != val2)
                        continue;
                    maxi = max(maxi, i.second + k.second - i.first.second / N * (j - last - 1));
                }
                last = j;
                upMax = 0, downMin = N - 1;
            }
            else
            {
                upMax = max(upMax, up[v1][j]);
                downMin = min(downMin, down[v1][j]);
            }
        }
        last = h1 - 1, upMax = 0, downMin = N - 1;
        for (int j = h1; j <= h2 + 1; j++)
        {
            if (j == h2 + 1 || F[v2 + 1][j] == 1)
            {
                if (last + 1 < j)
                {
                    int val1 = (j - last - 1) * N + (last + 1), val2 = (downMin - upMax - 1) * N + (upMax + 1);
                    int l = 0, r = mId - 1;
                    while (l != r)
                    {
                        int half = (l + r) / 2;
                        if (ans[half].first.first < val1 || (ans[half].first.first == val1 && ans[half].first.second < val2))
                        {
                            l = half + 1;
                        }
                        else
                        {
                            r = half;
                        }
                    }
                    const auto &k = ans[l];
                    if (k.first.first != val1 || k.first.second != val2)
                        continue;
                    maxi = max(maxi, i.second + k.second - i.first.second / N * (j - last - 1));
                }
                last = j;
                upMax = 0, downMin = N - 1;
            }
            else
            {
                upMax = max(upMax, up[v1][j]);
                downMin = min(downMin, down[v1][j]);
            }
        }

        ans[mId].second = maxi;
    }

    maxi = 0;
    for (int i = 0; i < where; i++)
        maxi = max(maxi, ans[i].second);
    return maxi;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 432 KB ok
4 Correct 0 ms 468 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 2 ms 2132 KB ok
8 Correct 55 ms 14612 KB ok
9 Correct 964 ms 132612 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 1 ms 340 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 0 ms 340 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 1 ms 304 KB ok
9 Correct 0 ms 340 KB ok
10 Correct 1 ms 340 KB ok
11 Correct 0 ms 340 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 1 ms 340 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 1 ms 340 KB ok
5 Correct 1 ms 340 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 1 ms 340 KB ok
9 Correct 1 ms 304 KB ok
10 Correct 0 ms 340 KB ok
11 Correct 1 ms 340 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 1 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 0 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 1 ms 340 KB ok
21 Correct 1 ms 340 KB ok
22 Correct 0 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 1 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 1 ms 340 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 432 KB ok
5 Correct 0 ms 468 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 0 ms 340 KB ok
9 Correct 1 ms 340 KB ok
10 Correct 1 ms 340 KB ok
11 Correct 1 ms 304 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 1 ms 340 KB ok
14 Correct 0 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 0 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 1 ms 340 KB ok
29 Correct 1 ms 340 KB ok
30 Correct 1 ms 840 KB ok
31 Correct 1 ms 852 KB ok
32 Correct 1 ms 820 KB ok
33 Correct 1 ms 724 KB ok
34 Correct 1 ms 852 KB ok
35 Correct 1 ms 812 KB ok
36 Correct 1 ms 852 KB ok
37 Correct 1 ms 852 KB ok
38 Correct 1 ms 820 KB ok
39 Correct 1 ms 820 KB ok
40 Correct 1 ms 816 KB ok
41 Correct 1 ms 852 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 432 KB ok
5 Correct 0 ms 468 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 0 ms 340 KB ok
9 Correct 1 ms 340 KB ok
10 Correct 1 ms 340 KB ok
11 Correct 1 ms 304 KB ok
12 Correct 0 ms 340 KB ok
13 Correct 1 ms 340 KB ok
14 Correct 0 ms 340 KB ok
15 Correct 0 ms 340 KB ok
16 Correct 1 ms 340 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 0 ms 340 KB ok
21 Correct 0 ms 340 KB ok
22 Correct 1 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 1 ms 340 KB ok
26 Correct 1 ms 340 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 1 ms 340 KB ok
29 Correct 1 ms 340 KB ok
30 Correct 1 ms 840 KB ok
31 Correct 1 ms 852 KB ok
32 Correct 1 ms 820 KB ok
33 Correct 1 ms 724 KB ok
34 Correct 1 ms 852 KB ok
35 Correct 1 ms 812 KB ok
36 Correct 1 ms 852 KB ok
37 Correct 1 ms 852 KB ok
38 Correct 1 ms 820 KB ok
39 Correct 1 ms 820 KB ok
40 Correct 1 ms 816 KB ok
41 Correct 1 ms 852 KB ok
42 Correct 87 ms 15276 KB ok
43 Correct 85 ms 15240 KB ok
44 Correct 84 ms 14340 KB ok
45 Correct 86 ms 14336 KB ok
46 Correct 80 ms 14668 KB ok
47 Correct 55 ms 14292 KB ok
48 Correct 57 ms 14300 KB ok
49 Correct 54 ms 14296 KB ok
50 Correct 60 ms 14296 KB ok
51 Correct 61 ms 14408 KB ok
52 Correct 48 ms 14304 KB ok
53 Correct 57 ms 14288 KB ok
54 Correct 48 ms 14272 KB ok
55 Correct 46 ms 14300 KB ok
56 Correct 46 ms 14300 KB ok
57 Correct 106 ms 15040 KB ok
58 Correct 101 ms 15052 KB ok
59 Correct 105 ms 15204 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB ok
2 Correct 0 ms 340 KB ok
3 Correct 0 ms 340 KB ok
4 Correct 0 ms 432 KB ok
5 Correct 0 ms 468 KB ok
6 Correct 0 ms 340 KB ok
7 Correct 1 ms 340 KB ok
8 Correct 2 ms 2132 KB ok
9 Correct 55 ms 14612 KB ok
10 Correct 964 ms 132612 KB ok
11 Correct 1 ms 340 KB ok
12 Correct 1 ms 340 KB ok
13 Correct 0 ms 340 KB ok
14 Correct 1 ms 340 KB ok
15 Correct 1 ms 340 KB ok
16 Correct 1 ms 304 KB ok
17 Correct 0 ms 340 KB ok
18 Correct 1 ms 340 KB ok
19 Correct 0 ms 340 KB ok
20 Correct 0 ms 340 KB ok
21 Correct 1 ms 340 KB ok
22 Correct 0 ms 340 KB ok
23 Correct 1 ms 340 KB ok
24 Correct 0 ms 340 KB ok
25 Correct 0 ms 340 KB ok
26 Correct 0 ms 340 KB ok
27 Correct 1 ms 340 KB ok
28 Correct 1 ms 340 KB ok
29 Correct 0 ms 340 KB ok
30 Correct 1 ms 340 KB ok
31 Correct 1 ms 340 KB ok
32 Correct 1 ms 340 KB ok
33 Correct 1 ms 340 KB ok
34 Correct 1 ms 340 KB ok
35 Correct 1 ms 840 KB ok
36 Correct 1 ms 852 KB ok
37 Correct 1 ms 820 KB ok
38 Correct 1 ms 724 KB ok
39 Correct 1 ms 852 KB ok
40 Correct 1 ms 812 KB ok
41 Correct 1 ms 852 KB ok
42 Correct 1 ms 852 KB ok
43 Correct 1 ms 820 KB ok
44 Correct 1 ms 820 KB ok
45 Correct 1 ms 816 KB ok
46 Correct 1 ms 852 KB ok
47 Correct 87 ms 15276 KB ok
48 Correct 85 ms 15240 KB ok
49 Correct 84 ms 14340 KB ok
50 Correct 86 ms 14336 KB ok
51 Correct 80 ms 14668 KB ok
52 Correct 55 ms 14292 KB ok
53 Correct 57 ms 14300 KB ok
54 Correct 54 ms 14296 KB ok
55 Correct 60 ms 14296 KB ok
56 Correct 61 ms 14408 KB ok
57 Correct 48 ms 14304 KB ok
58 Correct 57 ms 14288 KB ok
59 Correct 48 ms 14272 KB ok
60 Correct 46 ms 14300 KB ok
61 Correct 46 ms 14300 KB ok
62 Correct 106 ms 15040 KB ok
63 Correct 101 ms 15052 KB ok
64 Correct 105 ms 15204 KB ok
65 Correct 1588 ms 136144 KB ok
66 Correct 1122 ms 135468 KB ok
67 Correct 852 ms 130456 KB ok
68 Correct 1090 ms 126980 KB ok
69 Correct 1228 ms 129260 KB ok
70 Correct 1385 ms 131076 KB ok
71 Correct 1028 ms 126896 KB ok
72 Correct 992 ms 126620 KB ok
73 Correct 886 ms 126632 KB ok
74 Correct 1004 ms 126628 KB ok
75 Correct 936 ms 126620 KB ok
76 Correct 1110 ms 126644 KB ok
77 Correct 1022 ms 126740 KB ok
78 Correct 972 ms 128516 KB ok
79 Correct 850 ms 127440 KB ok
80 Correct 763 ms 127184 KB ok
81 Correct 872 ms 127188 KB ok
82 Correct 913 ms 127848 KB ok
83 Correct 1043 ms 130056 KB ok
84 Correct 757 ms 126620 KB ok
85 Correct 727 ms 126616 KB ok
86 Correct 788 ms 126612 KB ok
87 Correct 849 ms 126752 KB ok
88 Correct 955 ms 126764 KB ok
89 Correct 1006 ms 126644 KB ok
90 Correct 910 ms 126612 KB ok
91 Correct 939 ms 126644 KB ok
92 Correct 888 ms 128820 KB ok
93 Correct 893 ms 129176 KB ok
94 Correct 795 ms 127412 KB ok
95 Correct 770 ms 127020 KB ok
96 Correct 778 ms 126920 KB ok
97 Correct 768 ms 126732 KB ok
98 Correct 737 ms 126736 KB ok
99 Correct 1423 ms 138936 KB ok
100 Correct 4100 ms 138424 KB ok
101 Correct 4225 ms 137276 KB ok
102 Correct 4125 ms 138420 KB ok
103 Execution timed out 4531 ms 140412 KB Time limit exceeded
104 Halted 0 ms 0 KB -