✨

ABC 186 | F - Rook on Grid

2020/12/21に公開

競プロ

問題

解法

$1\leq H,W \leq 2\times 10^5$ なので貪欲に塗りつぶしていくとTLEになる。

駒は右が下しかしか移動できないので、右に移動してから下か、下に移動してから右に移動という2パターンしかない。
右->下に移動して到達できるマスの集合をAとし、下->右に移動して到達できるマスの集合をBとする。
AにもBにもあるマスがあるのでAとBを求めてからAにもBにもあるマスを引けば答えとなる。

0-indexedにして考えた例を図にすると以下である。

右->下に行くときを赤、下->右に行く時を青で表すと駒は以下のマスに到達できる。

AにもBにもあるマスを求めるにはセグメントツリーで右->下の区間を保持しながら下->右でその区間を順番にクエリすればいい。
順に行く際に、石にあたった場合はその区間の値を0にリセットする。

上記の赤と青の重なり部分をセグメントツリーをもとに順に求めると以下である。

コード

実装時のTips

0-indexedで実装する
セグメントツリーはAtCoder Libraryのものを使える

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int op(int a, int b) {
  return a + b;
}

int e() {
  return 0;
}

int main() {
  ll h, w, n;
  cin >> h >> w >> n;
  vector<int> a(w, h);  // 縦に見たときの最低の石の場所
  vector<int> b(h, w);  // 横にみたときの最低の石の場所
  for (int i = 0; i < n; i++) {
    int hi, wi;
    cin >> hi >> wi;
    hi--;
    wi--;
    a[wi] = min(a[wi], hi);
    b[hi] = min(b[hi], wi);
  }

  // Aは縦, Bは横
  // |A⋃B| = |A| + |B| + |A⋂B|
  ll ans = 0;
  // |A|
  for (int i = 0; i < b[0]; i++) {
    ans += a[i];
  }
  // |B|
  for (int i = 0; i < a[0]; i++) {
    ans += b[i];
  }
  segtree<int, op, e> seg(w);  // 0~w-1までで塗った範囲を入れていく
  for (int i = 0; i < b[0]; i++) {
    seg.set(i, 1);
  }
  vector<vector<int>> ends(h + 1);  // ends[i]: 縦で見たときにiで終わる石
  for (int i = 0; i < b[0]; i++) {
    ends[a[i]].push_back(i);
  }
  // 縦に移動しながら重なっている部分を引いていく
  for (int i = 0; i < a[0]; i++) {
    for (auto v : ends[i]) {
      seg.set(v, 0);
    }
    ans -= seg.prod(0, b[i]);
  }
  cout << ans << endl;
}

ABC 186 | F - Rook on Grid

問題

解法

コード

参考

Discussion