#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int linha_l[N], linha_r[N], coluna_l[N], coluna_r[N];
int linha_total[N], coluna_total[N];
int soma_linha[N], soma_coluna[N];
int pref_linha[N], pref_coluna[N];
int intercessao(int l1, int r1, int l2, int r2){
////cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
if(l1 > l2 or (l1 == l2 and r2 > r1)){
swap(l1, l2);
swap(r1, r2);
}
if(l1 > r2 or l2 > r1)
return 0;
if(l1 <= l2 and r2 <= r1){
return pref_linha[r2] - (l2 > 0 ? pref_linha[l2-1] : 0);
}
return pref_linha[r2] - (l1 > 0 ? pref_linha[l1-1] : 0);
}
int intercessao2(int l1, int r1, int l2, int r2){
if(l1 > l2 or (l1 == l2 and r2 > r1)){
swap(l1, l2);
swap(r1, r2);
}
if(l1 > r2 or l2 > r1)
return 0;
if(l1 <= l2 and r2 <= r1){
return pref_coluna[r2] - (l2 > 0 ? pref_coluna[l2-1] : 0);
}
return pref_coluna[r2] - (l1 > 0 ? pref_coluna[l1-1] : 0);
}
int biggest_stadium(int n, vector<vector<int>> m){
int tot = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
soma_linha[i] += (1-m[i][j]);
soma_coluna[j] += (1-m[i][j]);
}
}
pref_linha[0] = soma_linha[0];
pref_coluna[0] = soma_coluna[0];
for(int i = 1;i < n;i++){
pref_linha[i] = pref_linha[i-1] + soma_linha[i];
pref_coluna[i] = pref_coluna[i-1] + soma_coluna[i];
}
for(int i = 0;i < n;i++){
int aux = 0;
for(int j = 0;j < n;j++){
if(m[i][j] == 0){
tot++;
}
if(m[i][j] == 0 and aux == 0){
aux = 1;
}
if(m[i][j] == 1 and aux == 1){
aux = 2;
}
if(m[i][j] == 0 and aux == 2){
return 0;
}
}
}
for(int j = 0;j < n;j++){
int aux = 0;
for(int i = 0;i < n;i++){
if(m[i][j] == 0 and aux == 0){
aux = 1;
}
if(m[i][j] == 1 and aux == 1){
aux = 2;
}
if(m[i][j] == 0 and aux == 2){
return 0;
}
}
}
for(int i = 0;i < n;i++){
linha_l[i] = n+1, linha_r[i] = -1;
for(int j = 0;j < n;j++){
if(m[i][j] == 0){
linha_l[i] = min(linha_l[i], j);
linha_r[i] = max(linha_r[i], j);
}
}
////////cout << linha_l[i] << ' ' << linha_r[i] << '\n';
}
for(int j = 0;j < n; j++){
coluna_l[j] = n+1, coluna_r[j] = -1;
for(int i = 0;i < n;i++){
if(m[i][j] == 0){
coluna_l[j] = min(coluna_l[j], i);
coluna_r[j] = max(coluna_r[j], i);
}
}
////////cout << coluna_l[j] << ' ' << coluna_r[j] << '\n';
}
////////cout << tot << '\n';
for(int i = 0;i < n;i++){
int calc = 0;
for(int j = 0;j < n;j++){
if(m[i][j] == 0){
calc += coluna_r[j] - coluna_l[j]+1;
}
}
linha_total[i] = calc;
}
for(int j = 0;j < n;j++){
int calc = 0;
for(int i = 0;i < n;i++){
if(m[i][j] == 0){
calc += linha_r[i] - linha_l[i]+1;
}
}
coluna_total[j] = calc;
}
for(int i = 0;i < n;i++){
int l1 = linha_l[i], r1 = linha_r[i];
if(l1 > r1)
continue;
int small_coluna = l1;
for(int j = l1;j <= r1;j++){
if(coluna_l[j] < coluna_l[small_coluna])
small_coluna = j;
}
int big_coluna = l1;
for(int j = l1;j <= r1;j++){
if(coluna_r[j] > coluna_r[small_coluna])
big_coluna = j;
}
l1 = small_coluna;
r1 = big_coluna;
////cout << l1 << ' ' << r1 << '\n';
////cout << coluna_total[l1] << ' ' << coluna_total[r1] << '\n';
int ans = coluna_total[l1] + coluna_total[r1];
ans -= intercessao(coluna_l[l1], coluna_r[l1], coluna_l[r1], coluna_r[r1]);
////cout << ans << '\n';
if(ans != tot){
////cout << 1 << ' ';
////cout << i << '\n';
return 0;
}
}
for(int j = 0;j < n;j++){
int l1 = coluna_l[j], r1 = coluna_r[j];
if(l1 > r1)
continue;
int small_coluna = l1;
for(int i = l1;i <= r1;i++){
if(linha_l[i] < linha_l[small_coluna])
small_coluna = i;
}
int big_coluna = l1;
for(int i = l1;i <= r1;i++){
if(linha_r[i] > linha_r[small_coluna])
big_coluna = i;
}
l1 = small_coluna;
r1 = big_coluna;
int ans = linha_total[l1] + linha_total[r1];
//////cout << linha_total[l1] << ' ' << linha_total[r1] << '\n';
ans -= intercessao2(linha_l[l1], linha_r[l1], linha_l[r1], linha_r[r1]);
//////cout << ans << '\n';
if(ans != tot){
//cout << 2 << ' ';
//cout << j << '\n';
return 0;
}
}
return tot;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |