結果

問題 No.2574 Defect-free Rectangles
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-12-02 16:47:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,467 bytes
コンパイル時間 4,779 ms
コンパイル使用メモリ 272,480 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-26 20:43:02
合計ジャッジ時間 9,237 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 6 ms
5,376 KB
testcase_04 AC 6 ms
5,376 KB
testcase_05 AC 5 ms
5,376 KB
testcase_06 AC 465 ms
5,376 KB
testcase_07 AC 286 ms
5,376 KB
testcase_08 AC 274 ms
5,376 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

struct Fast {
  Fast() {
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(10);
  }
} fast;

#define all(a) (a).begin(), (a).end()
#define contains(a, x) ((a).find(x) != (a).end())
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)
#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";
#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";
#define yn(b) cout << ((b) ? "yes" : "no") << "\n";

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  }
  return os;
}

using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

using mint = modint998244353;
using vm = vector<mint>;
using vvm = vector<vm>;
inline ostream& operator<<(ostream& os, const mint P) { return os << P.val(); };

// https://satanic0258.github.io/snippets/data-structure/SegmentMap.html
class SegmentMap : public std::map<signed, signed> {
 private:
  bool flagToMergeAdjacentSegment;

 public:
  // if merge [l, c] and [c+1, r], set flagToMergeAdjacentSegment to true
  SegmentMap(bool flagToMergeAdjacentSegment) : flagToMergeAdjacentSegment(flagToMergeAdjacentSegment) {}
  // __exist -> iterator pair(l, r) (contain p)
  // noexist -> map.end()
  auto get(signed p) const {
    auto it = upper_bound(p);
    if (it == begin() || (--it)->second < p) return end();
    return it;
  }
  // insert segment [l, r]
  void insert(signed l, signed r) {
    auto itl = upper_bound(l), itr = upper_bound(r + flagToMergeAdjacentSegment);
    if (itl != begin()) {
      if ((--itl)->second < l - flagToMergeAdjacentSegment) ++itl;
    }
    if (itl != itr) {
      l = std::min(l, itl->first);
      r = std::max(r, std::prev(itr)->second);
      erase(itl, itr);
    }
    (*this)[l] = r;
  }
  // remove segment [l, r]
  void remove(signed l, signed r) {
    auto itl = upper_bound(l), itr = upper_bound(r);
    if (itl != begin()) {
      if ((--itl)->second < l) ++itl;
    }
    if (itl == itr) return;
    int tl = std::min(l, itl->first), tr = std::max(r, std::prev(itr)->second);
    erase(itl, itr);
    if (tl < l) (*this)[tl] = l - 1;
    if (r < tr) (*this)[r + 1] = tr;
  }
  // Is p and q in same segment?
  bool same(signed p, signed q) const {
    const auto&& it = get(p);
    return it != end() && it->first <= q && q <= it->second;
  }
};

void solve() {
  int h, w, n;
  cin >> h >> w >> n;
  vvi b(h, vi());
  rep(i, 0, n) {
    int u, v;
    cin >> u >> v;
    b[u - 1].push_back(v - 1);
  }

  ll ans = 0;
  rep(r, 0, h) {
    SegmentMap sm(true);
    sm.insert(0, w - 1);
    ll sum = (ll)w * (w + 1) / 2;
    vector<bool> f(w, false);
    rep(x, r, h) {
      for (auto y : b[x]) {
        if (f[y]) continue;
        f[y] = true;
        auto p = sm.get(y);
        if (p == sm.end()) continue;
        int l = (*p).first;
        int r = (*p).second + 1;
        ll d = r - l;
        sum -= d * (d + 1) / 2;
        ll d1 = y - l, d2 = r - (y + 1);
        sum += d1 * (d1 + 1) / 2 + d2 * (d2 + 1) / 2;
        sm.remove(y, y);
      }
      ans += sum;
    }
  }
  cout << ans << "\n";
}

int main() {
  int t = 1;
  // cin >> t;
  while (t--) solve();
}
0