結果

問題 No.2160 みたりのDominator
ユーザー KudeKude
提出日時 2022-12-11 17:52:44
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 447 ms / 2,000 ms
コード長 3,749 bytes
コンパイル時間 3,033 ms
コンパイル使用メモリ 254,224 KB
実行使用メモリ 30,928 KB
最終ジャッジ日時 2024-10-15 14:19:34
合計ジャッジ時間 16,892 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 93
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic pop
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
constexpr int INF = 1001001001;

struct S {
  int mn, mncnt;
  ll sm;
};
S op(S x, S y) {
  if (x.mn == y.mn) return S{x.mn, x.mncnt + y.mncnt, x.sm + y.sm};
  else return x.mn < y.mn ? x : y;
}
S e() { return S{INF, 0, 0}; }
struct F {
  int mnadd;
  int wadd;
};
F composition(F f, F g) { return F{f.mnadd + g.mnadd, f.wadd + g.wadd}; }
F id() { return {0, 0}; }
S mapping(F f, S x) {
  x.mn += f.mnadd;
  x.sm += (ll)x.mncnt * f.wadd;
  return x;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n1, n2, n3, m;
  cin >> n1 >> n2 >> n3 >> m;
  bool ok = true;
  vector<P> e11, e22, e33, e12, e13, e23;
  rep(_, m) {
    int u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);
    if (v <= n1) {
      e11.emplace_back(u, v);
    } else if (v <= n1 + n2) {
      if (u <= n1) e12.emplace_back(u, v - n1);
      else e22.emplace_back(u - n1, v - n1);
    } else if (v <= n1 + n2 + n3) {
      if (u <= n1) e13.emplace_back(u, v - (n1 + n2));
      else if (u <= n1 + n2) e23.emplace_back(u - n1, v - (n1 + n2));
      else e33.emplace_back(u - (n1 + n2), v - (n1 + n2));
    } else if (v == n1 + n2 + n3 + 1) {
      if (u <= n1) e11.emplace_back(0, u);
      else if (u <= n1 + n2) e22.emplace_back(0, u - n1);
      else e33.emplace_back(0, u - (n1 + n2));
    } else {
      if (u <= n1) e11.emplace_back(u, n1 + 1);
      else if (u <= n1 + n2) e22.emplace_back(u - n1, n2 + 1);
      else if (u <= n1 + n2 + n3) e33.emplace_back(u - (n1 + n2), n3 + 1);
      else ok = false;
    }
  }
  if (!ok) {
    cout << 0 << '\n';
    return 0;
  }
  n1++, n2++, n3++;
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S>(n2, S{0, 1, 0}));
  struct E {
    int l, r;
    F f;
  };
  vector<vector<E>> evs(n1 + 1);
  for(auto [i, j]: e12) {
    seg.apply(j, n2, F{1, 0});
    evs[i].push_back({0, n2, F{-1, 0}});
    evs[i].push_back({0, j, F{2, 0}});
  }
  for(auto [il, ir]: e11) {
    evs[il].push_back({0, n2, F{1, 0}});
    evs[ir].push_back({0, n2, F{-1, 0}});
  }
  for(auto [jl, jr]: e22) {
    seg.apply(jl, jr, F{1, 0});
  }
  VI k_bad(n3 + 1);
  for(auto [kl, kr]: e33) {
    k_bad[kl]++;
    k_bad[kr]--;
  }
  rep(i, n3) k_bad[i+1] += k_bad[i];
  multiset<int, greater<int>> imn{0}, jmn{0};
  multiset<int> imx{n1}, jmx{n2};
  VVI ev1(n3 + 1), ev2(n3 + 1);
  for(auto [i, k]: e13) {
    imx.insert(i);
    ev1[k].emplace_back(i);
  }
  for(auto [j, k]: e23) {
    jmx.insert(j);
    ev2[k].emplace_back(j);
  }
  rep(k, n3) {
    for(int i: ev1[k]) imx.erase(imx.find(i)), imn.insert(i);
    for(int j: ev2[k]) jmx.erase(jmx.find(j)), jmn.insert(j);
    if (k_bad[k]) continue;
    int il = *imn.begin(), jl = *jmn.begin();
    int ir = *imx.begin(), jr = *jmx.begin();
    if (il < ir && jl < jr) {
      evs[il].push_back({jl, jr, F{0, 1}});
      evs[ir].push_back({jl, jr, F{0, -1}});
    }
  }
  ll ans = 0;
  rep(i, n1) {
    for(auto [l, r, f]: evs[i]) seg.apply(l, r, f);
    auto p = seg.all_prod();
    if (p.mn == 0) ans += p.sm;
  }
  cout << ans << '\n';
}
0