oj.uz

Submission #839770

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

#include "soccer.h"

#include <algorithm>
#include <set>
#include <map>
#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;
set<pair<pair<pair<int, int>, pair<int, int>>, int>> ans;
int val[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];
set<pair<int, int>> trees[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];
    }

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

    for (int i = 1; i < N - 1; i++)
    {
        int last = 0;
        for (int j = 1; j < N; j++)
        {
            if (F[i][j] == 1)
            {
                if (last + 1 < j)
                    trees[i].insert({last, j});
                last = j;
            }
        }
    }

    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.insert({{{h, v}, {a + 1, bMost[pos] + 1}}, where});
                    val[where++] = v * h;
                }
            }
            block.insert(pos);
        }
    }

    for (auto i : ans)
    {
        maxi = val[i.second];

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

        int upMax = 0, downMin = 0;
        auto it = trees[v1 - 1].lower_bound({h1, -1});
        if (it != trees[v1 - 1].begin())
            it--;
        if (it != trees[v1 - 1].end() && (*it).second <= h1)
            it++;
        while (it != trees[v1 - 1].end() && (*it).first < h2)
        {
            int b = min(h2 + 1, (*it).second);
            int a = max(h1 - 1, (*it).first);
            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];
                }
                auto k = (*ans.lower_bound({{{b - a - 1, downMin - upMax - 1}, {a + 1, upMax + 1}}, -1}));
                maxi = max(maxi, val[i.second] + val[k.second] - i.first.first.second * k.first.first.first);
            }
            it++;
        }

        it = trees[v2 + 1].lower_bound({h1, -1});
        if (it != trees[v2 + 1].begin())
            it--;
        if (it != trees[v2 + 1].end() && (*it).second <= h1)
            it++;
        while (it != trees[v2 + 1].end() && (*it).first < h2)
        {
            int b = min(h2 + 1, (*it).second);
            int a = max(h1 - 1, (*it).first);
            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];
                }
                auto k = (*ans.lower_bound({{{b - a - 1, downMin - upMax - 1}, {a + 1, upMax + 1}}, -1}));
                maxi = max(maxi, val[i.second] + val[k.second] - i.first.first.second * k.first.first.first);
            }
            it++;
        }

        val[i.second] = maxi;
    }

    maxi = 0;
    for (int i = 0; i < where; i++)
        maxi = max(maxi, val[i]);
    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 0 ms 596 KB ok
2 Correct 0 ms 596 KB ok
3 Correct 1 ms 724 KB ok
4 Correct 1 ms 852 KB ok
5 Correct 0 ms 468 KB ok
6 Correct 1 ms 596 KB ok
7 Correct 4 ms 4052 KB ok
8 Correct 66 ms 26708 KB ok
9 Correct 1070 ms 222980 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 0 ms 596 KB ok
3 Correct 0 ms 596 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 852 KB ok
6 Correct 0 ms 596 KB ok
7 Correct 1 ms 596 KB ok
8 Correct 1 ms 580 KB ok
9 Correct 1 ms 584 KB ok
10 Correct 1 ms 584 KB ok
11 Correct 1 ms 584 KB ok
12 Correct 1 ms 580 KB ok
13 Correct 1 ms 596 KB ok
14 Correct 1 ms 596 KB ok
15 Correct 1 ms 584 KB ok
16 Correct 0 ms 596 KB ok
17 Correct 1 ms 724 KB ok
18 Correct 1 ms 724 KB ok
19 Correct 1 ms 724 KB ok
20 Correct 1 ms 724 KB ok
21 Correct 2 ms 724 KB ok
22 Correct 1 ms 724 KB ok
23 Correct 1 ms 724 KB ok
24 Correct 1 ms 724 KB ok
25 Correct 1 ms 724 KB ok
26 Correct 1 ms 724 KB ok
27 Correct 1 ms 712 KB ok
28 Correct 0 ms 724 KB ok
29 Correct 1 ms 724 KB ok
30 Correct 2 ms 1492 KB ok
31 Correct 2 ms 1492 KB ok
32 Correct 1 ms 1492 KB ok
33 Correct 1 ms 1492 KB ok
34 Correct 2 ms 1492 KB ok
35 Correct 3 ms 1328 KB ok
36 Correct 1 ms 1364 KB ok
37 Correct 1 ms 1364 KB ok
38 Correct 1 ms 1364 KB ok
39 Correct 1 ms 1364 KB ok
40 Correct 1 ms 1352 KB ok
41 Correct 2 ms 1480 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 0 ms 596 KB ok
3 Correct 0 ms 596 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 852 KB ok
6 Correct 0 ms 596 KB ok
7 Correct 1 ms 596 KB ok
8 Correct 1 ms 580 KB ok
9 Correct 1 ms 584 KB ok
10 Correct 1 ms 584 KB ok
11 Correct 1 ms 584 KB ok
12 Correct 1 ms 580 KB ok
13 Correct 1 ms 596 KB ok
14 Correct 1 ms 596 KB ok
15 Correct 1 ms 584 KB ok
16 Correct 0 ms 596 KB ok
17 Correct 1 ms 724 KB ok
18 Correct 1 ms 724 KB ok
19 Correct 1 ms 724 KB ok
20 Correct 1 ms 724 KB ok
21 Correct 2 ms 724 KB ok
22 Correct 1 ms 724 KB ok
23 Correct 1 ms 724 KB ok
24 Correct 1 ms 724 KB ok
25 Correct 1 ms 724 KB ok
26 Correct 1 ms 724 KB ok
27 Correct 1 ms 712 KB ok
28 Correct 0 ms 724 KB ok
29 Correct 1 ms 724 KB ok
30 Correct 2 ms 1492 KB ok
31 Correct 2 ms 1492 KB ok
32 Correct 1 ms 1492 KB ok
33 Correct 1 ms 1492 KB ok
34 Correct 2 ms 1492 KB ok
35 Correct 3 ms 1328 KB ok
36 Correct 1 ms 1364 KB ok
37 Correct 1 ms 1364 KB ok
38 Correct 1 ms 1364 KB ok
39 Correct 1 ms 1364 KB ok
40 Correct 1 ms 1352 KB ok
41 Correct 2 ms 1480 KB ok
42 Correct 163 ms 31320 KB ok
43 Correct 166 ms 32772 KB ok
44 Correct 87 ms 27844 KB ok
45 Correct 76 ms 27368 KB ok
46 Correct 115 ms 29548 KB ok
47 Correct 71 ms 26876 KB ok
48 Correct 64 ms 25704 KB ok
49 Correct 66 ms 25684 KB ok
50 Correct 73 ms 29720 KB ok
51 Correct 97 ms 28720 KB ok
52 Correct 51 ms 23304 KB ok
53 Correct 58 ms 22160 KB ok
54 Correct 59 ms 23496 KB ok
55 Correct 59 ms 24792 KB ok
56 Correct 69 ms 23704 KB ok
57 Correct 89 ms 31220 KB ok
58 Correct 101 ms 31600 KB ok
59 Correct 135 ms 32272 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB ok
2 Correct 0 ms 596 KB ok
3 Correct 0 ms 596 KB ok
4 Correct 1 ms 724 KB ok
5 Correct 1 ms 852 KB ok
6 Correct 0 ms 468 KB ok
7 Correct 1 ms 596 KB ok
8 Correct 4 ms 4052 KB ok
9 Correct 66 ms 26708 KB ok
10 Correct 1070 ms 222980 KB ok
11 Correct 0 ms 596 KB ok
12 Correct 1 ms 596 KB ok
13 Correct 1 ms 580 KB ok
14 Correct 1 ms 584 KB ok
15 Correct 1 ms 584 KB ok
16 Correct 1 ms 584 KB ok
17 Correct 1 ms 580 KB ok
18 Correct 1 ms 596 KB ok
19 Correct 1 ms 596 KB ok
20 Correct 1 ms 584 KB ok
21 Correct 0 ms 596 KB ok
22 Correct 1 ms 724 KB ok
23 Correct 1 ms 724 KB ok
24 Correct 1 ms 724 KB ok
25 Correct 1 ms 724 KB ok
26 Correct 2 ms 724 KB ok
27 Correct 1 ms 724 KB ok
28 Correct 1 ms 724 KB ok
29 Correct 1 ms 724 KB ok
30 Correct 1 ms 724 KB ok
31 Correct 1 ms 724 KB ok
32 Correct 1 ms 712 KB ok
33 Correct 0 ms 724 KB ok
34 Correct 1 ms 724 KB ok
35 Correct 2 ms 1492 KB ok
36 Correct 2 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 3 ms 1328 KB ok
41 Correct 1 ms 1364 KB ok
42 Correct 1 ms 1364 KB ok
43 Correct 1 ms 1364 KB ok
44 Correct 1 ms 1364 KB ok
45 Correct 1 ms 1352 KB ok
46 Correct 2 ms 1480 KB ok
47 Correct 163 ms 31320 KB ok
48 Correct 166 ms 32772 KB ok
49 Correct 87 ms 27844 KB ok
50 Correct 76 ms 27368 KB ok
51 Correct 115 ms 29548 KB ok
52 Correct 71 ms 26876 KB ok
53 Correct 64 ms 25704 KB ok
54 Correct 66 ms 25684 KB ok
55 Correct 73 ms 29720 KB ok
56 Correct 97 ms 28720 KB ok
57 Correct 51 ms 23304 KB ok
58 Correct 58 ms 22160 KB ok
59 Correct 59 ms 23496 KB ok
60 Correct 59 ms 24792 KB ok
61 Correct 69 ms 23704 KB ok
62 Correct 89 ms 31220 KB ok
63 Correct 101 ms 31600 KB ok
64 Correct 135 ms 32272 KB ok
65 Execution timed out 4612 ms 293300 KB Time limit exceeded
66 Halted 0 ms 0 KB -