#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
int biggest_stadium(int n, vvi f) {
vvi up(n, vi(n)), down(n, vi(n)), left(n, vi(n)), right(n, vi(n));
loop(x, n) {
up[0][x] = 1 - f[0][x];
for (int y = 1; y < n; y++) {
if (f[y][x])
up[y][x] = 0;
else
up[y][x] = up[y - 1][x] + 1;
}
down[n - 1][x] = 1 - f[n - 1][x];
for (int y = n - 2; y >= 0; y--) {
if (f[y][x])
down[y][x] = 0;
else
down[y][x] = down[y + 1][x] + 1;
}
}
loop(y, n) {
left[y][0] = 1 - f[y][0];
for (int x = 1; x < n; x++) {
if (f[y][x])
left[y][x] = 0;
else
left[y][x] = left[y][x - 1] + 1;
}
right[y][n - 1] = 1 - f[y][n - 1];
for (int x = n - 2; x >= 0; x--) {
if (f[y][x])
right[y][x] = 0;
else
right[y][x] = right[y][x + 1] + 1;
}
//loop(y, n)
// cout << high[x][y] << low[x][y] << ' ';
//cout << endl;
}
//cout << endl;
int result = 0;
loop(y, n) {
loop(x, n) {
if (f[y][x]) {
cerr << "00 ";
continue;
}
int count1 = 0;
{
int l = 0, r = n - 1;
vii intervals;
for (int y2 = y; y2 < y + down[y][x]; y2++) {
l = max(l, x - left[y2][x] + 1);
r = min(r, x + right[y2][x] - 1);
intervals.push_back({ l, r });
count1 += r - l + 1;
}
l = x - left[y][x] + 1;
r = x + right[y][x] - 1;
int idx = 0;
for (int y2 = y - 1; y2 > y - up[y][x]; y2--) {
l = max(l, x - left[y2][x] + 1);
r = min(r, x + right[y2][x] - 1);
while (idx < intervals.size()) {
auto [li, ri] = intervals[idx];
if (r < ri)
l = max(l, li);
if (l > li)
r = min(r, ri);
if (li >= l && ri <= r)
break;
idx++;
}
if (r < l)
break;
count1 += r - l + 1;
}
}
int count2 = 0;
{
int l = 0, r = n - 1;
vii intervals;
for (int y2 = y; y2 > y - up[y][x]; y2--) {
l = max(l, x - left[y2][x] + 1);
r = min(r, x + right[y2][x] - 1);
intervals.push_back({ l, r });
count2 += r - l + 1;
}
l = x - left[y][x] + 1;
r = x + right[y][x] - 1;
int idx = 0;
for (int y2 = y + 1; y2 < y + down[y][x]; y2++) {
l = max(l, x - left[y2][x] + 1);
r = min(r, x + right[y2][x] - 1);
while (idx < intervals.size()) {
auto [li, ri] = intervals[idx];
if (r < ri)
l = max(l, li);
if (l > li)
r = min(r, ri);
if (li >= l && ri <= r)
break;
idx++;
}
if (r < l)
break;
count2 += r - l + 1;
}
}
int count3 = 0;
{
int l = 0, r = n - 1;
vii intervals;
for (int x2 = x; x2 < x + right[y][x]; x2++) {
l = max(l, y - up[y][x2] + 1);
r = min(r, y + down[y][x2] - 1);
intervals.push_back({ l, r });
count3 += r - l + 1;
}
l = x - left[y][x] + 1;
r = x + right[y][x] - 1;
int idx = 0;
for (int x2 = x - 1; x2 > x - left[y][x]; x2--) {
l = max(l, x - left[y][x2] + 1);
r = min(r, x + right[y][x2] - 1);
while (idx < intervals.size()) {
auto [li, ri] = intervals[idx];
if (r < ri)
l = max(l, li);
if (l > li)
r = min(r, ri);
if (li >= l && ri <= r)
break;
idx++;
}
if (r < l)
break;
count3 += r - l + 1;
}
}
int count4 = 0;
{
int l = 0, r = n - 1;
vii intervals;
for (int x2 = x; x2 > x - left[y][x]; x2--) {
l = max(l, y - up[y][x2] + 1);
r = min(r, y + down[y][x2] - 1);
intervals.push_back({ l, r });
count4 += r - l + 1;
}
l = x - left[y][x] + 1;
r = x + right[y][x] - 1;
int idx = 0;
for (int x2 = x + 1; x2 < x + right[y][x]; x2++) {
l = max(l, x - left[y][x2] + 1);
r = min(r, x + right[y][x2] - 1);
while (idx < intervals.size()) {
auto [li, ri] = intervals[idx];
if (r < ri)
l = max(l, li);
if (l > li)
r = min(r, ri);
if (li >= l && ri <= r)
break;
idx++;
}
if (r < l)
break;
count4 += r - l + 1;
}
}
int count = max({ count1, count2, count3, count4} );
result = max(result, count);
cerr << count / 10 << count % 10 << ' ';
}
cerr << endl;
}
return result;
}
Compilation message
soccer.cpp: In function 'int biggest_stadium(int, vvi)':
soccer.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while (idx < intervals.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:144:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | while (idx < intervals.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:183:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | while (idx < intervals.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:222:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | while (idx < intervals.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
1 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
0 ms |
348 KB |
ok |
| 6 |
Partially correct |
0 ms |
348 KB |
partial |
| 7 |
Partially correct |
69 ms |
728 KB |
partial |
| 8 |
Correct |
3584 ms |
8020 KB |
ok |
| 9 |
Execution timed out |
4568 ms |
102964 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
ok |
| 2 |
Correct |
0 ms |
348 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 |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Incorrect |
0 ms |
348 KB |
wrong |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Incorrect |
0 ms |
348 KB |
wrong |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Incorrect |
0 ms |
348 KB |
wrong |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
ok |
| 2 |
Correct |
0 ms |
348 KB |
ok |
| 3 |
Correct |
0 ms |
348 KB |
ok |
| 4 |
Correct |
1 ms |
348 KB |
ok |
| 5 |
Correct |
1 ms |
348 KB |
ok |
| 6 |
Correct |
0 ms |
348 KB |
ok |
| 7 |
Partially correct |
0 ms |
348 KB |
partial |
| 8 |
Partially correct |
69 ms |
728 KB |
partial |
| 9 |
Correct |
3584 ms |
8020 KB |
ok |
| 10 |
Execution timed out |
4568 ms |
102964 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
