Submission #1040244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040244		erray	Soccer Stadium (IOI23_soccer)	C++17	14 / 100	1273 ms	481448 KiB

soccer

#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;
    }
  }
  debug(sum, block_D, block_L, block_R);
  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, mid) == 0;
    }) + 1;
    int t = find_last(-1, c, [&](int mid) {
      return Rect(l, r, mid, c) != 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;
      debug(i, l, r);
      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});
      }
      auto[t, b] = Range_col(i, l, r);
      debug(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("top", 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("bot", 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];
      }
      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
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30