結果

問題 No.2574 Defect-free Rectangles
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-12-02 16:37:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,175 bytes
コンパイル時間 4,184 ms
コンパイル使用メモリ 277,344 KB
実行使用メモリ 10,644 KB
最終ジャッジ日時 2023-12-02 16:38:06
合計ジャッジ時間 8,854 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,548 KB
testcase_01 AC 2 ms
6,548 KB
testcase_02 AC 2 ms
6,548 KB
testcase_03 AC 5 ms
6,548 KB
testcase_04 AC 6 ms
6,548 KB
testcase_05 AC 5 ms
6,548 KB
testcase_06 AC 412 ms
6,548 KB
testcase_07 AC 266 ms
6,548 KB
testcase_08 AC 225 ms
6,548 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(); };

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) {
    vector<bool> f(w, false);
    set<int> ls;
    ls.insert(0);
    map<int, int> mp;
    mp[0] = w;
    ll sum = (ll)w * (w + 1) / 2;
    rep(x, r, h) {
      for (auto y : b[x]) {
        if (f[y]) continue;
        f[y] = true;
        auto it = ls.lower_bound(y + 1);
        if (it == ls.begin()) continue;
        it--;
        int l = *it;
        int r = mp[l];
        if (r <= y) continue;

        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;
        // [l,y),[y+1,r)
        if (l < y) {
          mp[l] = y;
        } else {
          ls.erase(l);
        }
        if (y + 1 < r) {
          ls.insert(y + 1);
          mp[y + 1] = r;
        }
      }
      ans += sum;
    }
  }
  cout << ans << "\n";
}

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