#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);
//cout << R << " : (" << rect_s.count(R) << ") " << rect_s[R] << '\n';
if(ul.j < last_tree){rect R = rect(ul,dr);rect_s[R];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
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] << ", ";}
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
ok |
| 2 |
Incorrect |
0 ms |
348 KB |
wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
1 ms |
344 KB |
ok |
| 3 |
Incorrect |
0 ms |
348 KB |
wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
