oj.uz

Submission #1042869

# Submission time Handle Problem Language Result Execution time Memory
1042869 2024-08-03T13:40:57 Z ZanP Soccer Stadium (IOI23_soccer) C++17
29.5 / 100
 2032 ms 873472 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;

struct point{
    int i, j;
    point(){}
    point(int i, int j){
        this->i = i; this->j = j;
    }
};
struct rect{
    point ul, dr;
    rect(){}
    rect(point ul, point dr){this->ul = ul, this->dr = dr;}
};
bool operator==(const point & a, const point & b){return a.i == b.i && a.j == b.j;}
bool operator==(const rect & a, const rect & b){return a.ul == b.ul && a.dr == b.dr;}
bool operator!=(const rect & a, const rect & b){return !(a.ul == b.ul && a.dr == b.dr);}
bool operator<(const rect & a, const rect & b){
    int h_a = a.dr.i - a.ul.i + 1, h_b = b.dr.i - b.ul.i + 1;
    if(h_a == h_b){
        if(a.ul.j == b.ul.j){
            return a.ul.i < b.ul.i;
        }
        return a.ul.j < b.ul.j;
    }
    return h_a < h_b;
}

ostream& operator<<(ostream& os, vector<int> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}
ostream& operator<<(ostream& os, vector<vector<int>> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}
ostream& operator<<(ostream& os, point & a){
    os << "(" << a.i << "," << a.j << ")";
    return os;
}

ostream& operator<<(ostream& os, rect & a){
    os << "{" << a.ul << "," << a.dr << "}";
    return os;
}
ostream& operator<<(ostream& os, vector<rect> & a){
    os << "{ ";
    for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
    os << "}\n";
    return os;
}


vector<vector<int>> look_up, look_down, look_right, look_left;
vector<int> lg;
vector<vector<vector<int>>> rmq_up, rmq_down;

int get_rmq_up(int i, int l, int r){
    int k = lg[r - l + 1];
    return min(rmq_up[i][l][k], rmq_up[i][r - (1 << k) + 1][k]);
}

int get_rmq_down(int i, int l, int r){
    int k = lg[r - l + 1];
    return min(rmq_down[i][l][k], rmq_down[i][r - (1 << k) + 1][k]);
}

int biggest_stadium(int n, vector<vector<int>> grid)
{
    look_up.resize(n,vector<int>(n));
    look_down.resize(n,vector<int>(n));
    look_right.resize(n,vector<int>(n));
    look_left.resize(n,vector<int>(n));
    for(int j = 0;j<n;j++){
        look_up[0][j] = 1 - grid[0][j];
        look_down[n-1][j] = 1 - grid[n-1][j];
        look_left[j][0] = 1 - grid[j][0];
        look_right[j][n-1] = 1 - grid[j][n-1];
    }

    for(int i = 1; i < n; i++){
        for(int j = 0;j < n; j++){
            look_up[i][j] = (grid[i][j]) ? 0 : 1 + look_up[i-1][j];
            look_down[n-i-1][j] = (grid[n-i-1][j]) ? 0 : 1 + look_down[n-i][j];
            look_left[j][i] = (grid[j][i]) ? 0 : 1 + look_left[j][i-1];
            look_right[j][n-i-1] = (grid[j][n-i-1]) ? 0 : 1 + look_right[j][n-i];
        }
    }

    lg.resize(n+1,0);
    for(int i = 2; i<=n;i++){lg[i] = 1 + lg[i>>1];}

    //cout << look_up << '\n' << look_down << '\n' << look_right << '\n' << look_left << '\n';

    rmq_up.resize(n,vector<vector<int>>(n,vector<int>(lg[n]+1)));
    rmq_down.resize(n,vector<vector<int>>(n,vector<int>(lg[n]+1)));
    for(int i = 0;i<n;i++)for(int j = 0;j<n;j++){
        rmq_up[i][j][0] = look_up[i][j];
        rmq_down[i][j][0] = look_down[i][j];
    }

    for(int k = 1; k <= lg[n]; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j + (1 << (k-1)) < n; j++){
                rmq_up[i][j][k] = min(rmq_up[i][j][k-1], rmq_up[i][j + (1 << (k-1))][k-1]);
                rmq_down[i][j][k] = min(rmq_down[i][j][k-1], rmq_down[i][j + (1 << (k-1))][k-1]);
            }
        }
    }

    map<rect,int> rect_s;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(grid[i][j])continue;
            int l = j - look_left[i][j] + 1, r = j + look_right[i][j] - 1;
            int up = i - get_rmq_up(i,l,r) + 1, down = i + get_rmq_down(i,l,r) - 1;
            rect R = rect(point(up,l), point(down,r));
            //cout << R << " : (" << rect_s.count(R) << ") " << rect_s[R] << '\n';
            rect_s[R] = rect_s.size();
        }
    }

    //cout << "rects:\n";
    int xx = 0;
    int m = rect_s.size();
    vector<rect> rects(m);
    for(pair<const rect, int> & p : rect_s){
        p.second = xx;
        rect a = p.first;
        rects[xx] = a;
        xx++;
    }
    //cout << rects << '\n';

    vector<vector<int>> pov(m);
    for(int i = 0;i<m;i++){
        rect a = rects[i];
        if(a.ul.i > 0){
            for(int l = a.ul.j, r = l; l<=a.dr.j;l=r+1){
                int i_i = a.ul.i-1;
                if(grid[i_i][l]){r = l;continue;}
                r = min(l + look_right[i_i][l] - 1, a.dr.j);
                int up = i_i - get_rmq_up(i_i,l,r) + 1, down = i_i + get_rmq_down(i_i,l,r) - 1;
                rect R = rect(point(up,l), point(down,r));
                if(rect_s.count(R))pov[i].push_back(rect_s[R]);
            }
        }
        if(a.dr.i < n-1){
            for(int l = a.ul.j, r = l; l<=a.dr.j;l=r+1){
                int i_i = a.dr.i+1;
                if(grid[i_i][l]){r = l; continue;}
                r = min(l + look_right[i_i][l] - 1, a.dr.j);
                int up = i_i - get_rmq_up(i_i,l,r) + 1, down = i_i + get_rmq_down(i_i,l,r) - 1;
                rect R = rect(point(up,l), point(down,r));
                if(rect_s.count(R))pov[i].push_back(rect_s[R]);
            }
        }
    }
    
    //cout << pov << '\n';

    vector<int> dp(m,0);
    int ans = 0;
    for(int i = 0; i < m; i++)
    {
        rect a = rects[i];
        int S = (a.dr.i - a.ul.i + 1) * (a.dr.j - a.ul.j + 1);
        S = max(S,dp[i]);
        dp[i] = S;
        for(int & b_i : pov[i]){
            rect b = rects[b_i];
            int Sb = (b.dr.i - b.ul.i - a.dr.i + a.ul.i) * (b.dr.j - b.ul.j + 1);
            dp[b_i] = max(Sb + S, dp[b_i]);
        }
        ans = max(ans, dp[i]);
    }
    //cout << dp << '\n';
    return ans;
}

// int main(){
//      cout << 
//      biggest_stadium(5, {{0, 0, 0, 1, 0},
//                          {1, 0, 1, 0, 0},
//                          {0, 0, 0, 0, 0},
//                          {1, 0, 0, 0, 0},
//                          {0, 1, 0, 1, 0}}) << '\n';
//  }

Compilation message

soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
soccer.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::vector<int> >&)':
soccer.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~
soccer.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<rect>&)':
soccer.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0; i<a.size(); i++){os << a[i] << ", ";}
      |                    ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 440 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 3 ms 1884 KB ok
8 Correct 52 ms 42180 KB ok
9 Correct 940 ms 791632 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Partially correct 0 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 408 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
5.5 / 22.0

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

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 408 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 436 KB ok
18 Partially correct 0 ms 348 KB partial
19 Partially correct 0 ms 348 KB partial
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Partially correct 0 ms 348 KB partial
27 Partially correct 0 ms 348 KB partial
28 Partially correct 0 ms 348 KB partial
29 Partially correct 1 ms 348 KB partial
30 Correct 1 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 1 ms 352 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Partially correct 0 ms 348 KB partial
38 Partially correct 1 ms 348 KB partial
39 Partially correct 0 ms 348 KB partial
40 Correct 0 ms 348 KB ok
41 Partially correct 0 ms 348 KB partial

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 408 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 436 KB ok
18 Partially correct 0 ms 348 KB partial
19 Partially correct 0 ms 348 KB partial
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Partially correct 0 ms 348 KB partial
27 Partially correct 0 ms 348 KB partial
28 Partially correct 0 ms 348 KB partial
29 Partially correct 1 ms 348 KB partial
30 Correct 1 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 1 ms 352 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Partially correct 0 ms 348 KB partial
38 Partially correct 1 ms 348 KB partial
39 Partially correct 0 ms 348 KB partial
40 Correct 0 ms 348 KB ok
41 Partially correct 0 ms 348 KB partial
42 Partially correct 94 ms 44880 KB partial
43 Partially correct 104 ms 46932 KB partial
44 Partially correct 67 ms 42320 KB partial
45 Partially correct 62 ms 42184 KB partial
46 Partially correct 76 ms 43440 KB partial
47 Partially correct 55 ms 42064 KB partial
48 Correct 55 ms 42068 KB ok
49 Partially correct 53 ms 42068 KB partial
50 Correct 72 ms 42692 KB ok
51 Correct 64 ms 44048 KB ok
52 Partially correct 47 ms 42064 KB partial
53 Partially correct 55 ms 42068 KB partial
54 Partially correct 50 ms 42064 KB partial
55 Partially correct 52 ms 42064 KB partial
56 Correct 48 ms 42068 KB ok
57 Partially correct 52 ms 42076 KB partial
58 Partially correct 59 ms 42064 KB partial
59 Partially correct 61 ms 42064 KB partial

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 428 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 440 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 3 ms 1884 KB ok
9 Correct 52 ms 42180 KB ok
10 Correct 940 ms 791632 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 348 KB ok
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 408 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 1 ms 348 KB ok
22 Correct 0 ms 436 KB ok
23 Partially correct 0 ms 348 KB partial
24 Partially correct 0 ms 348 KB partial
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 348 KB ok
30 Correct 0 ms 348 KB ok
31 Partially correct 0 ms 348 KB partial
32 Partially correct 0 ms 348 KB partial
33 Partially correct 0 ms 348 KB partial
34 Partially correct 1 ms 348 KB partial
35 Correct 1 ms 348 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 1 ms 352 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 348 KB ok
42 Partially correct 0 ms 348 KB partial
43 Partially correct 1 ms 348 KB partial
44 Partially correct 0 ms 348 KB partial
45 Correct 0 ms 348 KB ok
46 Partially correct 0 ms 348 KB partial
47 Partially correct 94 ms 44880 KB partial
48 Partially correct 104 ms 46932 KB partial
49 Partially correct 67 ms 42320 KB partial
50 Partially correct 62 ms 42184 KB partial
51 Partially correct 76 ms 43440 KB partial
52 Partially correct 55 ms 42064 KB partial
53 Correct 55 ms 42068 KB ok
54 Partially correct 53 ms 42068 KB partial
55 Correct 72 ms 42692 KB ok
56 Correct 64 ms 44048 KB ok
57 Partially correct 47 ms 42064 KB partial
58 Partially correct 55 ms 42068 KB partial
59 Partially correct 50 ms 42064 KB partial
60 Partially correct 52 ms 42064 KB partial
61 Correct 48 ms 42068 KB ok
62 Partially correct 52 ms 42076 KB partial
63 Partially correct 59 ms 42064 KB partial
64 Partially correct 61 ms 42064 KB partial
65 Partially correct 2032 ms 836056 KB partial
66 Correct 1819 ms 873472 KB ok
67 Correct 1217 ms 826996 KB ok
68 Partially correct 1117 ms 792316 KB partial
69 Partially correct 1262 ms 796648 KB partial
70 Partially correct 1383 ms 802640 KB partial
71 Partially correct 1155 ms 792236 KB partial
72 Partially correct 1016 ms 791680 KB partial
73 Correct 968 ms 791804 KB ok
74 Correct 970 ms 791744 KB ok
75 Partially correct 943 ms 791612 KB partial
76 Correct 1169 ms 799828 KB ok
77 Correct 1175 ms 799712 KB ok
78 Partially correct 1300 ms 810832 KB partial
79 Correct 1032 ms 799312 KB ok
80 Partially correct 982 ms 796936 KB partial
81 Partially correct 997 ms 795472 KB partial
82 Partially correct 1043 ms 797396 KB partial
83 Partially correct 1381 ms 822264 KB partial
84 Partially correct 917 ms 791684 KB partial
85 Partially correct 930 ms 791804 KB partial
86 Partially correct 903 ms 791908 KB partial
87 Partially correct 907 ms 791708 KB partial
88 Correct 888 ms 791632 KB ok
89 Partially correct 960 ms 791888 KB partial
90 Partially correct 1006 ms 791632 KB partial
91 Partially correct 982 ms 791640 KB partial
92 Correct 1166 ms 811828 KB ok
93 Correct 1163 ms 816468 KB ok
94 Correct 1018 ms 799060 KB ok
95 Correct 962 ms 795380 KB ok
96 Partially correct 977 ms 794372 KB partial
97 Partially correct 975 ms 793572 KB partial
98 Partially correct 933 ms 792656 KB partial
99 Correct 1356 ms 810564 KB ok
100 Partially correct 1118 ms 792148 KB partial
101 Partially correct 1075 ms 792144 KB partial
102 Partially correct 1095 ms 792104 KB partial
103 Partially correct 1094 ms 792196 KB partial
104 Partially correct 1078 ms 792060 KB partial
105 Partially correct 1083 ms 792148 KB partial
106 Partially correct 1183 ms 792148 KB partial
107 Correct 1087 ms 792044 KB ok
108 Correct 1125 ms 794756 KB ok
109 Correct 1133 ms 794252 KB ok