Submission #1043478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043478		ZanP	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	3155 ms	974296 KiB

soccer

#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)
{
    //cout << grid << '\n';
    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;
 
/*  MAKING RECTANGLES :

    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();
 
            up = i - look_up[i][j] + 1; down = i + look_down[i][j] - 1;
            l = j - get_rmq_left(j,up,down) + 1; r = j + get_rmq_right(j,up,down) - 1;
            R = rect(point(up,l), point(down, r));
            //cout << R << " : (" << rect_s.count(R) << ") " << rect_s[R] << '\n';
            rect_s[R] = rect_s.size();
        }
    }
*/ 

    for(int i = 0; i<n;i++){
        vector<pair<int,int>> stack; stack.reserve(n+2);
        int last_tree = -1;
        stack.push_back({-1,0});
        for(int j = 0;j<=n;j++){
            int up = (j == n) ? 0 : look_up[i][j];
            while(!stack.empty()){
                if(up > stack.back().second){break;}
                pair<int,int> p = stack.back(); stack.pop_back();
                if(p.second != up){
                   point ul = point(i - p.second + 1, stack.back().first+1);
                   point dr = point(i, j-1);
                   rect R = rect(ul,dr);
                   if(ul.j <= last_tree){
                    rect_s[R] = 0;
                    } 
                }
            }
            if(j == n){break;}
            if(look_down[i][j] == 1){
                last_tree = j;
            }
            stack.push_back({j,up});
        }
    }

    //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},
//                         {0, 0, 1, 1, 0},
//                         {0, 0, 0, 1, 0},
//                         {1, 0, 0, 0, 0},
//                         {0, 1, 1, 1, 1}}) << '\n';
// }

Compilation message (stderr)

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
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 30 / 30