oj.uz

Submission #1040252

# Submission time Handle Problem Language Result Execution time Memory
1040252 2024-07-31T20:29:49 Z erray Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2758 ms 519356 KB 
#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi23_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename F> 
int find_last(int l, int r, F f) {
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (f(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}
template<typename T> 
bool ckmax(T& a, T b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
  vector<vector<int>> sum(N + 1, vector<int>(N + 1));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      sum[i + 1][j + 1] = F[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
    }
  }
  vector<vector<int>> block_D(N + 1, vector<int>(N, -1));
  vector<vector<int>> block_L(N, vector<int>(N, -1)), block_R(N, vector<int>(N, N));
  for (int i = N - 1; i >= 0; --i) {
    for (int j = 0; j < N; ++j) {
      block_D[i][j] = block_D[i + 1][j];
      if (F[i][j]) block_D[i][j] = i;
    }
    for (int j = 0; j < N; ++j) {
      if (j > 0) block_L[i][j] = block_L[i][j - 1];
      if (F[i][j]) block_L[i][j] = j;
    }
    for (int j = N - 1; j >= 0; --j) {
      if (j < N - 1) block_R[i][j] = block_R[i][j + 1];
      if (F[i][j]) block_R[i][j] = j;
    }
  }
  auto Rect = [&](int l, int r, int t, int b) {
    return (sum[b + 1][r + 1] + sum[t][l] - sum[b + 1][l] - sum[t][r + 1]);
  };
  auto Range_col = [&](int c, int l, int r) -> array<int, 2> {
    int b = find_last(c, N - 1, [&](int mid) {
      return Rect(l, r, c + 1, mid) == 0;
    }) + 1;
    int t = find_last(-1, c - 1, [&](int mid) {
      return Rect(l, r, mid, c - 1) != 0;
    });
    return {t, b};
  };
  auto Range_row = [&](int r, int u, int d) -> array<int, 2> {
    int l = find_last(-1, r, [&](int mid) {
      return Rect(mid, r, u, d) != 0;
    });
    int rr = find_last(r, N - 1, [&](int mid) {
      return Rect(r, mid, u, d) == 0;
    }) + 1;
    return {l, rr};
  };
  
  vector<vector<vector<array<int, 3>>>> to_L(N, vector<vector<array<int, 3>>>(N)), to_R(N, vector<vector<array<int, 3>>>(N));
  vector<vector<array<int, 3>>> bucket(N);
  for (int i = N - 1; i >= 0; --i) {
    int last = -1;
    for (int j = 0; j <= N; ++j) {
      if (j != N && !F[i][j]) continue;
      int l = last + 1, r = j - 1;
      last = j;
      if (l > r) continue;
      for (int ll = l; ll <= r; ++ll) {
        bucket[r - ll].push_back({~i, ll, r});
      }
      for (int rr = l; rr <= r; ++rr) {
        bucket[rr - l].push_back({i, l, rr});
      }
      if (l == 0 || r == N - 1) continue;
      auto[t, b] = Range_col(i, l - 1, r + 1);
      debug(l, r, t, b);
      if (t + 1 != i) {
        auto[range_l, range_r] = Range_row(l, t + 1, i - 1);
        int l_row = (range_l == -1 ? t + 1 : block_D[t + 1][range_l]);
        int r_row = (range_r == N ? t + 1 : block_D[t + 1][range_r]);
        debug("t", range_l, range_r, l_row, r_row);
        if (r < N - 1) to_L[l_row][r + 1].push_back({i, l, r});
        if (l > 0) to_R[r_row][l - 1].push_back({i, l, r});
      }
      if (i + 1 != b) {
        auto[range_l, range_r] = Range_row(l, i + 1, b - 1);
        int l_row = (range_l == -1 ? i + 1 : block_D[i + 1][range_l]);
        int r_row = (range_r == N ? i + 1 : block_D[i + 1][range_r]);
        debug("b", range_l, range_r, l_row, r_row);
        if (r < N - 1) to_L[l_row][r + 1].push_back({i, l, r});
        if (l > 0) to_R[r_row][l - 1].push_back({i, l, r});
      }
    }
  } 
  debug(to_L);
  debug(to_R);
  debug(bucket);  
  vector<vector<int>> L(N, vector<int>(N)), R(N, vector<int>(N));
  auto Add_L = [&](int row, int r, int val, int len) {
    int l = block_L[row][r];
    if (l != r) ckmax(L[row][r], val - len * (r - l));
  };
  auto Add_R = [&](int row, int l, int val, int len) {
    int r = block_R[row][l];
    if (l != r) ckmax(R[row][l], val - len * (r - l));
  };
  vector<vector<int>> len_L(N, vector<int>(N));
  vector<vector<int>> len_R = len_L, mx_L = len_L, mx_R = len_L; 
  
  int ans = 0;;
  for (int len = N - 1; len >= 0; --len) {
    vector<int> L_max(N), R_max(N);
    for (auto[row, l, r] : bucket[len]) {
      auto[t, b] = Range_col(row < 0 ? ~row : row, l, r);
      int len = b - t - 1;
      int val;
      int between_upd;
      vector<array<int, 3>> upds;
      
      if (row < 0) {
        row = ~row;
        val = R[row][l] + (r - l + 1) * len;
        int prev = R_max[r];
        R_max[r] = val;
        int pos = (r + 1 == N ? row + 1 : block_D[row + 1][r + 1]);
        if (pos < b) {
          ckmax(R_max[r], prev);
        }
        if (len_R[row][r] != len) {
          len_R[row][r] = len;
          mx_R[row][r] = 0;
        }
        ckmax(mx_R[row][r], R_max[r]);
        between_upd = mx_R[row][r];
        upds = to_R[row][l];
      } else {
        val = L[row][r] + (r - l + 1) * len;
        int prev = L_max[l];
        L_max[l] = val;
        int pos = (l - 1 == -1 ? row + 1 : block_D[row + 1][l - 1]);
        if (pos < b) {
          ckmax(L_max[l], prev);
        }
        if (len_L[row][l] != len) {
          len_L[row][l] = len;
          mx_L[row][l] = 0;
        }
        ckmax(mx_L[row][l], L_max[l]);
        between_upd = mx_L[row][l];
        upds = to_L[row][r];
      }
      debug(between_upd, upds);
      for (auto[next_row, next_l, next_r] : upds) {
        Add_L(next_row, next_r, between_upd, len);
        Add_R(next_row, next_l, between_upd, len);
      }
      ans = max(ans, val);
      debug(row, l, r, t, b, val);
      if (t >= 0) {
        Add_L(t, r, val, len);
        Add_R(t, l, val, len);
      }
      if (b < N) {
        Add_L(b, r, val, len);
        Add_R(b, l, val, len);
      }
    }
  }
  return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 432 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 2 ms 1628 KB ok
8 Correct 68 ms 30728 KB ok
9 Correct 1253 ms 481360 KB ok

Subtask #2
8.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 1 ms 348 KB ok
4 Correct 0 ms 436 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 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 0 ms 436 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 0 ms 348 KB ok
10 Correct 0 ms 348 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 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 600 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 436 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 Correct 1 ms 344 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 432 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 436 KB ok
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 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 600 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 436 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 Correct 1 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 360 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 1 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 440 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 432 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 432 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 436 KB ok
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 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 0 ms 600 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 436 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 Correct 1 ms 344 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 0 ms 360 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 1 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 0 ms 440 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 0 ms 432 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 84 ms 31472 KB ok
43 Correct 72 ms 30776 KB ok
44 Correct 87 ms 32092 KB ok
45 Correct 96 ms 32356 KB ok
46 Correct 90 ms 31632 KB ok
47 Correct 68 ms 31068 KB ok
48 Correct 47 ms 28508 KB ok
49 Correct 48 ms 28756 KB ok
50 Correct 67 ms 33040 KB ok
51 Correct 74 ms 30716 KB ok
52 Correct 26 ms 25684 KB ok
53 Correct 23 ms 25176 KB ok
54 Correct 26 ms 25740 KB ok
55 Correct 33 ms 26460 KB ok
56 Correct 42 ms 27732 KB ok
57 Correct 97 ms 32080 KB ok
58 Correct 95 ms 32080 KB ok
59 Correct 79 ms 32088 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 432 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 2 ms 1628 KB ok
9 Correct 68 ms 30728 KB ok
10 Correct 1253 ms 481360 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 436 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 KB ok
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 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 348 KB ok
23 Correct 0 ms 600 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 436 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 Correct 1 ms 344 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 360 KB ok
35 Correct 0 ms 348 KB ok
36 Correct 1 ms 348 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 0 ms 440 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 0 ms 432 KB ok
43 Correct 1 ms 348 KB ok
44 Correct 1 ms 344 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 0 ms 348 KB ok
47 Correct 84 ms 31472 KB ok
48 Correct 72 ms 30776 KB ok
49 Correct 87 ms 32092 KB ok
50 Correct 96 ms 32356 KB ok
51 Correct 90 ms 31632 KB ok
52 Correct 68 ms 31068 KB ok
53 Correct 47 ms 28508 KB ok
54 Correct 48 ms 28756 KB ok
55 Correct 67 ms 33040 KB ok
56 Correct 74 ms 30716 KB ok
57 Correct 26 ms 25684 KB ok
58 Correct 23 ms 25176 KB ok
59 Correct 26 ms 25740 KB ok
60 Correct 33 ms 26460 KB ok
61 Correct 42 ms 27732 KB ok
62 Correct 97 ms 32080 KB ok
63 Correct 95 ms 32080 KB ok
64 Correct 79 ms 32088 KB ok
65 Correct 2324 ms 492196 KB ok
66 Correct 682 ms 416968 KB ok
67 Correct 444 ms 394492 KB ok
68 Correct 1880 ms 503632 KB ok
69 Correct 2536 ms 491300 KB ok
70 Correct 2758 ms 491932 KB ok
71 Correct 1787 ms 499540 KB ok
72 Correct 1701 ms 481620 KB ok
73 Correct 1004 ms 443780 KB ok
74 Correct 1127 ms 444936 KB ok
75 Correct 1040 ms 444496 KB ok
76 Correct 1453 ms 519356 KB ok
77 Correct 1421 ms 519112 KB ok
78 Correct 1886 ms 488028 KB ok
79 Correct 437 ms 391084 KB ok
80 Correct 442 ms 391024 KB ok
81 Correct 551 ms 397380 KB ok
82 Correct 863 ms 412180 KB ok
83 Correct 762 ms 407268 KB ok
84 Correct 412 ms 397528 KB ok
85 Correct 368 ms 392712 KB ok
86 Correct 495 ms 403024 KB ok
87 Correct 503 ms 404068 KB ok
88 Correct 764 ms 431956 KB ok
89 Correct 1703 ms 472576 KB ok
90 Correct 1226 ms 450200 KB ok
91 Correct 1427 ms 475108 KB ok
92 Correct 554 ms 399772 KB ok
93 Correct 631 ms 397560 KB ok
94 Correct 477 ms 393908 KB ok
95 Correct 457 ms 394540 KB ok
96 Correct 447 ms 394868 KB ok
97 Correct 465 ms 394920 KB ok
98 Correct 369 ms 390284 KB ok
99 Correct 2007 ms 484860 KB ok
100 Correct 1588 ms 500236 KB ok
101 Correct 1483 ms 500344 KB ok
102 Correct 1585 ms 500164 KB ok
103 Correct 1492 ms 500064 KB ok
104 Correct 1516 ms 500692 KB ok
105 Correct 1738 ms 500972 KB ok
106 Correct 1514 ms 502036 KB ok
107 Correct 1516 ms 503720 KB ok
108 Correct 1182 ms 471856 KB ok
109 Correct 1254 ms 473972 KB ok