Submission #1148957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148957		cot7302	Furniture (JOI20_furniture)	C++20	100 / 100	174 ms	14304 KiB

furniture

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

constexpr int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vec<vec<int>> ind(N + 2, vec<int>(M + 2, infty<int>)), oud(N + 2, vec<int>(M + 2, infty<int>));
  vec<vec<int>> placed(N + 2, vec<int>(M + 2));
  vec<int> cnt(N + M + 1);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      ind[i][j] = 2;
      oud[i][j] = 2;
      cnt[i + j] += 1;
    }
  }
  auto add = [&](int __i, int __j) {
    if (placed[__i][__j]) {
      return true;
    }
    if (cnt[__i + __j] == 1) {
      return false;
    }
    queue<pair<int, int>> q;
    q.emplace(__i, __j);
    while (!empty(q)) {
      auto [i, j] = q.front(); q.pop();
      if (placed[i][j]) {
        continue;
      }
      placed[i][j] = 1;
      cnt[i + j] -= 1;
      for (auto [di, dj] : dir) {
        int ni = i + di, nj = j + dj;
        if (di < 0 || dj < 0) {
          if (--oud[ni][nj] == 0) {
            q.emplace(ni, nj);
          }
        }
        else {
          if (--ind[ni][nj] == 0) {
            q.emplace(ni, nj);
          }
        }
      }
    }
    return true;
  };
  for (int i = 0; i <= N + 1; i++) {
    placed[i][0] = 1;
    placed[i][M + 1] = 1;
    ind[i][1] -= 1;
    oud[i][M] -= 1;
  }
  for (int j = 0; j <= M + 1; j++){
    placed[0][j] = 1;
    placed[N + 1][j] = 1;
    ind[1][j] -= 1;
    oud[N][j] -= 1;
  }
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      int x; cin >> x;
      if (x == 1) {
        add(i, j);
      }
    }
  }
  int Q; cin >> Q;
  while (Q--) {
    int x, y; cin >> x >> y;
    cout << add(x, y) << '\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95