結果

問題 No.3369 Find MyakuMyaku
コンテスト
ユーザー Naru820
提出日時 2025-11-16 05:21:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 266 ms / 2,000 ms
コード長 2,664 bytes
コンパイル時間 5,576 ms
コンパイル使用メモリ 335,156 KB
実行使用メモリ 64,720 KB
最終ジャッジ日時 2025-11-17 20:48:06
合計ジャッジ時間 13,381 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define rep(i, n) for (ll i = 0; i < ll(n); i++)

struct Square {
  ll x_min, x_max, y_min, y_max;
};

void remove(atcoder::dsu &dsu, ll h, ll w, ll idx, vector<bool> &occupied) {
  ll x = idx / (w + 2);
  ll y = idx % (w + 2);
  /*
  cerr << "Removing cell at (" << x << ", " << y << ") with index " << idx
  << endl;
  */
  vector<pair<ll, ll>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  for (auto [dx, dy] : directions) {
    ll nx = x + dx;
    ll ny = y + dy;
    if (nx >= 0 && nx < h + 2 && ny >= 0 && ny < w + 2) {
      ll nidx = nx * (w + 2) + ny;
      if (occupied[nidx])
        continue;
      dsu.merge(idx, nidx);
    }
  }
  return;
}

int main() {
  ll n, h, w;
  cin >> n >> h >> w;
  vector<Square> squares(n);
  rep(i, n) {
    cin >> squares[i].x_min >> squares[i].x_max >> squares[i].y_min >>
        squares[i].y_max;
    squares[i].x_min--;
    squares[i].y_min--;
  }
  set<ll> pos_inner_init;
  rep(i, w + 1) { pos_inner_init.insert(i); }
  vector<set<ll>> pos(h + 1, pos_inner_init);
  vector<vector<ll>> remove_cache(n);
  vector<bool> occupied((h + 2) * (w + 2), false);
  ll occupied_count = 0;
  rep(i, n) {
    // cerr << "Processing square " << i << endl;
    for (ll x = squares[i].x_min; x < squares[i].x_max; x++) {
      ll left = (squares[i].y_min);
      ll right = (squares[i].y_max);
      auto it = pos[x].lower_bound(left);
      vector<ll> removal_list;
      while (it != pos[x].end() && *it < right) {
        /*
        cerr << "Marking cell at (" << x << ", " << *it << ") for removal"
        << endl;
        */
        ll y = *it;
        ll idx = (x + 1) * (w + 2) + (y + 1);
        remove_cache[i].push_back(idx);
        occupied[idx] = true;
        occupied_count++;
        removal_list.push_back(y);
        it++;
      }
      for (ll y : removal_list) {
        pos[x].erase(y);
      }
    }
  }
  atcoder::dsu dsu((h + 2) * (w + 2));
  rep(i, (h + 2) * (w + 2)) {
    if (!occupied[i]) {
      remove(dsu, h, w, i, occupied);
    }
  }
  vector<bool> ans(n);
  for (ll i = n - 1; i >= 0; i--) {
    /*
    cerr << "Calculating answer for removal " << i << endl;
    cerr << "Current occupied count: " << occupied_count << endl;
    cerr << "Current dsu size of leader(0): " << dsu.size(dsu.leader(0))
    << endl;
    */
    ans[i] = (dsu.size(dsu.leader(0)) + occupied_count) != ((h + 2) * (w + 2));
    for (ll idx : remove_cache[i]) {
      occupied_count--;
      remove(dsu, h, w, idx, occupied);
      occupied[idx] = false;
    }
  }
  rep(i, n) { cout << (ans[i] ? "Yes" : "No") << endl; }
}
0