Submission #1056977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056977		juicy	Garden (JOI23_garden)	C++17	100 / 100	488 ms	15956 KiB

garden

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e3;

int n, m, d, ma;
int L[N], R[N], lst[N];
bool A[2 * N], B[N], flg[N];
bitset<N> G[2 * N];
vector<int> g[2 * N];

void bld() {
  ma = 0;
  for (int i = 0; i < 2 * d; ++i) {
    g[i].clear();
  }
  fill(flg, flg + d, 0);
}

void tog(int i) {
  int l = !i ? d - 1 : i - 1, r = i + 1 == d ? 0 : i + 1;
  l = flg[l] ? L[l] : i, r = flg[r] ? R[r] : i;
  flg[i] = 1;
  L[r] = l, R[l] = r;
  ma = max(ma, r - l + 1 + (r < l ? d : 0));
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> d;
  while (n--) {
    int x, y; cin >> x >> y;
    A[x] = A[x + d] = 1;
    B[y] = 1;
  }
  while (m--) {
    int x, y; cin >> x >> y;
    if (!A[x] && !B[y]) {
      G[x][y] = G[x + d][y] = 1;
    }
  }
  int res = d * d;
  for (int i = 0; i < d; ++i) {
    if (!A[i]) {
      int j = i; 
      while (j < 2 * d && !A[j]) {
        ++j;
      }
      fill(lst, lst + d, -1);
      for (int l = j - 1; l >= i; --l) {
        for (int k = 0; k < d; ++k) {
          if (G[l][k]) {
            lst[k] = l;
          }
        }
        bld();
        for (int k = 0; k < d; ++k) {
          if (~lst[k]) {
            g[lst[k]].push_back(k);
          } else if (!B[k]) {
            tog(k);
          }
        }
        for (int r = j - 1; r >= l; --r) {
          res = min(res, (d - r + l - 1) * (d - ma));
          for (auto x : g[r]) {
            tog(x);
          }
        }
        res = min(res, d * (d - ma));
      }
      i = j - 1;
    }
  }
  cout << res;
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25