oj.uz

Submission #839769

# Submission time Handle Problem Language Result Execution time Memory
839769 2023-08-30T15:50:44 Z model_code Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2182 ms 291500 KB 
// correct/BM_bigRec_N2log.cpp

#include "soccer.h"

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

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 upLeft[MAXN][MAXN];
int upRight[MAXN][MAXN];
int down[MAXN][MAXN];
int downLeft[MAXN][MAXN];
int downRight[MAXN][MAXN];
int sum[MAXN][MAXN];
int nxt[2][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;
            down[i][j] = N - 1;
            downLeft[i][j] = N - 1;
            downRight[i][j] = N - 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];
    }

    for (int i = 0; i < N; i++)
    {
        nxt[0][i][N - 1] = nxt[1][i][N - 1] = N;
        for (int j = N - 2; j >= 0; j--)
        {
            int nxt_elem = F[i][j + 1];

            nxt[nxt_elem][i][j] = j + 1;
            nxt[1 - nxt_elem][i][j] = nxt[1 - nxt_elem][i][j + 1];
        }
    }

    bMost[0] = -1;
    bMost[N - 1] = -1;
    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 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 = 1; i < N - 1; i++)
    {
        for (int j = 1; j < N - 1; j++)
        {
            up[i][j] = up[i - 1][j];
            if (F[i][j] == 1)
            {
                up[i][j] = i;
            }
            else
            {
                upLeft[i][j] = max(upLeft[i][j - 1], up[i][j]);
            }
        }
        for (int j = N - 2; j > 0; j--)
        {
            if (F[i][j] == 0)
            {
                upRight[i][j] = max(upRight[i][j + 1], up[i][j]);
            }
        }
    }
    for (int i = N - 2; i > 0; i--)
    {
        for (int j = 1; j < N - 1; j++)
        {
            down[i][j] = down[i + 1][j];
            if (F[i][j] == 1)
            {
                down[i][j] = i;
            }
            else
            {
                downLeft[i][j] = min(downLeft[i][j - 1], down[i][j]);
            }
        }
        for (int j = N - 2; j > 0; j--)
        {
            if (F[i][j] == 0)
            {
                downRight[i][j] = min(downRight[i][j + 1], down[i][j]);
            }
        }
    }
    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 upMax = 0, downMin = 0;
        int x = h1 - 1;
        while (x < h2)
        {
            int xx = nxt[0][v1 - 1][x];
            int yy = (xx == N ? N : nxt[1][v1 - 1][xx] - 1);
            x = yy;
            int b = min(h2 + 1, yy + 1);
            int a = max(h1 - 1, xx - 1);
            // std::cerr<<v1<<" "<<v2<<" "<<h1<<" "<<h2<<" "<<a<<" "<<b<<"\n";
            if (a + 1 < b)
            {
                if (a == h1 - 1)
                {
                    upMax = upRight[v1 - 1][a + 1], downMin = downRight[v1 - 1][a + 1];
                }
                else
                {
                    upMax = upLeft[v1 - 1][b - 1], downMin = downLeft[v1 - 1][b - 1];
                }
                int val1 = (b - a - 1) * N + (a + 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 * (b - a - 1));
            }
        }

        x = h1 - 1;
        while (x < h2)
        {
            int xx = nxt[0][v2 + 1][x];
            int yy = (xx == N ? N : nxt[1][v2 + 1][xx] - 1);
            x = yy;
            int b = min(h2 + 1, yy + 1);
            int a = max(h1 - 1, xx - 1);
            // std::cerr<<v1<<" "<<v2<<" "<<h1<<" "<<h2<<" "<<a<<" "<<b<<"\n";
            if (a + 1 < b)
            {
                if (a == h1 - 1)
                {
                    upMax = upRight[v2 + 1][a + 1], downMin = downRight[v2 + 1][a + 1];
                }
                else
                {
                    upMax = upLeft[v2 + 1][b - 1], downMin = downLeft[v2 + 1][b - 1];
                }
                int val1 = (b - a - 1) * N + (a + 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 * (b - a - 1));
            }
        }
        // std::cerr<<v1<<" "<<v2<<" "<<h1<<" "<<h2<<" "<<maxi<<"!!\n";
        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 1 ms 596 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB ok
2 Correct 0 ms 468 KB ok
3 Correct 1 ms 724 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 340 KB ok
6 Correct 1 ms 468 KB ok
7 Correct 5 ms 4808 KB ok
8 Correct 67 ms 32516 KB ok
9 Correct 1112 ms 269036 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 1 ms 468 KB ok
3 Correct 0 ms 468 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 1 ms 524 KB ok
7 Correct 1 ms 468 KB ok
8 Correct 1 ms 468 KB ok
9 Correct 1 ms 468 KB ok
10 Correct 1 ms 468 KB ok
11 Correct 1 ms 468 KB ok
12 Correct 1 ms 468 KB ok
13 Correct 1 ms 468 KB ok
14 Correct 1 ms 468 KB ok
15 Correct 1 ms 468 KB ok
16 Correct 0 ms 468 KB ok
17 Correct 1 ms 596 KB ok
18 Correct 1 ms 596 KB ok
19 Correct 1 ms 696 KB ok
20 Correct 1 ms 596 KB ok
21 Correct 1 ms 596 KB ok
22 Correct 0 ms 596 KB ok
23 Correct 1 ms 640 KB ok
24 Correct 1 ms 596 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 1 ms 596 KB ok
27 Correct 1 ms 596 KB ok
28 Correct 1 ms 596 KB ok
29 Correct 1 ms 596 KB ok
30 Correct 1 ms 1620 KB ok
31 Correct 2 ms 1620 KB ok
32 Correct 1 ms 1596 KB ok
33 Correct 3 ms 1492 KB ok
34 Correct 2 ms 1592 KB ok
35 Correct 1 ms 1492 KB ok
36 Correct 1 ms 1492 KB ok
37 Correct 1 ms 1492 KB ok
38 Correct 1 ms 1492 KB ok
39 Correct 2 ms 1492 KB ok
40 Correct 2 ms 1464 KB ok
41 Correct 1 ms 1620 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 1 ms 468 KB ok
3 Correct 0 ms 468 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 1 ms 524 KB ok
7 Correct 1 ms 468 KB ok
8 Correct 1 ms 468 KB ok
9 Correct 1 ms 468 KB ok
10 Correct 1 ms 468 KB ok
11 Correct 1 ms 468 KB ok
12 Correct 1 ms 468 KB ok
13 Correct 1 ms 468 KB ok
14 Correct 1 ms 468 KB ok
15 Correct 1 ms 468 KB ok
16 Correct 0 ms 468 KB ok
17 Correct 1 ms 596 KB ok
18 Correct 1 ms 596 KB ok
19 Correct 1 ms 696 KB ok
20 Correct 1 ms 596 KB ok
21 Correct 1 ms 596 KB ok
22 Correct 0 ms 596 KB ok
23 Correct 1 ms 640 KB ok
24 Correct 1 ms 596 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 1 ms 596 KB ok
27 Correct 1 ms 596 KB ok
28 Correct 1 ms 596 KB ok
29 Correct 1 ms 596 KB ok
30 Correct 1 ms 1620 KB ok
31 Correct 2 ms 1620 KB ok
32 Correct 1 ms 1596 KB ok
33 Correct 3 ms 1492 KB ok
34 Correct 2 ms 1592 KB ok
35 Correct 1 ms 1492 KB ok
36 Correct 1 ms 1492 KB ok
37 Correct 1 ms 1492 KB ok
38 Correct 1 ms 1492 KB ok
39 Correct 2 ms 1492 KB ok
40 Correct 2 ms 1464 KB ok
41 Correct 1 ms 1620 KB ok
42 Correct 122 ms 33340 KB ok
43 Correct 111 ms 33380 KB ok
44 Correct 81 ms 32868 KB ok
45 Correct 92 ms 32704 KB ok
46 Correct 105 ms 33072 KB ok
47 Correct 77 ms 32732 KB ok
48 Correct 71 ms 31564 KB ok
49 Correct 65 ms 31540 KB ok
50 Correct 69 ms 32664 KB ok
51 Correct 80 ms 32772 KB ok
52 Correct 64 ms 29192 KB ok
53 Correct 55 ms 28036 KB ok
54 Correct 58 ms 29388 KB ok
55 Correct 60 ms 30636 KB ok
56 Correct 67 ms 29572 KB ok
57 Correct 80 ms 33480 KB ok
58 Correct 84 ms 33524 KB ok
59 Correct 87 ms 33600 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 1 ms 468 KB ok
3 Correct 0 ms 468 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 724 KB ok
6 Correct 1 ms 340 KB ok
7 Correct 1 ms 468 KB ok
8 Correct 5 ms 4808 KB ok
9 Correct 67 ms 32516 KB ok
10 Correct 1112 ms 269036 KB ok
11 Correct 1 ms 524 KB ok
12 Correct 1 ms 468 KB ok
13 Correct 1 ms 468 KB ok
14 Correct 1 ms 468 KB ok
15 Correct 1 ms 468 KB ok
16 Correct 1 ms 468 KB ok
17 Correct 1 ms 468 KB ok
18 Correct 1 ms 468 KB ok
19 Correct 1 ms 468 KB ok
20 Correct 1 ms 468 KB ok
21 Correct 0 ms 468 KB ok
22 Correct 1 ms 596 KB ok
23 Correct 1 ms 596 KB ok
24 Correct 1 ms 696 KB ok
25 Correct 1 ms 596 KB ok
26 Correct 1 ms 596 KB ok
27 Correct 0 ms 596 KB ok
28 Correct 1 ms 640 KB ok
29 Correct 1 ms 596 KB ok
30 Correct 1 ms 596 KB ok
31 Correct 1 ms 596 KB ok
32 Correct 1 ms 596 KB ok
33 Correct 1 ms 596 KB ok
34 Correct 1 ms 596 KB ok
35 Correct 1 ms 1620 KB ok
36 Correct 2 ms 1620 KB ok
37 Correct 1 ms 1596 KB ok
38 Correct 3 ms 1492 KB ok
39 Correct 2 ms 1592 KB ok
40 Correct 1 ms 1492 KB ok
41 Correct 1 ms 1492 KB ok
42 Correct 1 ms 1492 KB ok
43 Correct 1 ms 1492 KB ok
44 Correct 2 ms 1492 KB ok
45 Correct 2 ms 1464 KB ok
46 Correct 1 ms 1620 KB ok
47 Correct 122 ms 33340 KB ok
48 Correct 111 ms 33380 KB ok
49 Correct 81 ms 32868 KB ok
50 Correct 92 ms 32704 KB ok
51 Correct 105 ms 33072 KB ok
52 Correct 77 ms 32732 KB ok
53 Correct 71 ms 31564 KB ok
54 Correct 65 ms 31540 KB ok
55 Correct 69 ms 32664 KB ok
56 Correct 80 ms 32772 KB ok
57 Correct 64 ms 29192 KB ok
58 Correct 55 ms 28036 KB ok
59 Correct 58 ms 29388 KB ok
60 Correct 60 ms 30636 KB ok
61 Correct 67 ms 29572 KB ok
62 Correct 80 ms 33480 KB ok
63 Correct 84 ms 33524 KB ok
64 Correct 87 ms 33600 KB ok
65 Correct 2071 ms 282540 KB ok
66 Correct 1351 ms 282436 KB ok
67 Correct 1127 ms 276584 KB ok
68 Correct 1272 ms 274580 KB ok
69 Correct 1553 ms 276656 KB ok
70 Correct 1692 ms 279564 KB ok
71 Correct 1207 ms 272588 KB ok
72 Correct 1167 ms 273240 KB ok
73 Correct 1020 ms 258508 KB ok
74 Correct 966 ms 258416 KB ok
75 Correct 1010 ms 257876 KB ok
76 Correct 1058 ms 273844 KB ok
77 Correct 1090 ms 272252 KB ok
78 Correct 1127 ms 274820 KB ok
79 Correct 1088 ms 270816 KB ok
80 Correct 1008 ms 271104 KB ok
81 Correct 1050 ms 269160 KB ok
82 Correct 1148 ms 271124 KB ok
83 Correct 1351 ms 275740 KB ok
84 Correct 851 ms 233636 KB ok
85 Correct 832 ms 229156 KB ok
86 Correct 885 ms 235896 KB ok
87 Correct 850 ms 238220 KB ok
88 Correct 947 ms 246172 KB ok
89 Correct 1071 ms 267360 KB ok
90 Correct 1055 ms 260896 KB ok
91 Correct 1016 ms 266604 KB ok
92 Correct 978 ms 273128 KB ok
93 Correct 1154 ms 275228 KB ok
94 Correct 979 ms 271344 KB ok
95 Correct 948 ms 267832 KB ok
96 Correct 898 ms 267728 KB ok
97 Correct 893 ms 266728 KB ok
98 Correct 891 ms 260020 KB ok
99 Correct 2182 ms 286092 KB ok
100 Correct 1511 ms 283340 KB ok
101 Correct 1409 ms 284992 KB ok
102 Correct 1338 ms 284708 KB ok
103 Correct 1630 ms 289312 KB ok
104 Correct 1586 ms 289540 KB ok
105 Correct 1623 ms 290228 KB ok
106 Correct 1638 ms 291500 KB ok
107 Correct 1611 ms 291012 KB ok
108 Correct 1197 ms 275704 KB ok
109 Correct 1092 ms 275580 KB ok