結果

問題 No.2160 みたりのDominator
ユーザー KudeKude
提出日時 2022-12-11 17:52:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 456 ms / 2,000 ms
コード長 3,749 bytes
コンパイル時間 3,490 ms
コンパイル使用メモリ 243,588 KB
実行使用メモリ 31,040 KB
最終ジャッジ日時 2024-04-23 14:11:43
合計ジャッジ時間 16,723 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 44 ms
20,708 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 35 ms
31,040 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 2 ms
5,376 KB
testcase_40 AC 154 ms
22,764 KB
testcase_41 AC 136 ms
21,876 KB
testcase_42 AC 80 ms
14,052 KB
testcase_43 AC 119 ms
19,520 KB
testcase_44 AC 150 ms
22,348 KB
testcase_45 AC 137 ms
21,836 KB
testcase_46 AC 109 ms
20,376 KB
testcase_47 AC 59 ms
12,784 KB
testcase_48 AC 80 ms
17,332 KB
testcase_49 AC 86 ms
19,276 KB
testcase_50 AC 68 ms
18,492 KB
testcase_51 AC 88 ms
15,068 KB
testcase_52 AC 129 ms
21,016 KB
testcase_53 AC 149 ms
22,220 KB
testcase_54 AC 81 ms
14,056 KB
testcase_55 AC 446 ms
27,268 KB
testcase_56 AC 328 ms
22,812 KB
testcase_57 AC 384 ms
24,696 KB
testcase_58 AC 448 ms
29,120 KB
testcase_59 AC 428 ms
25,932 KB
testcase_60 AC 344 ms
28,380 KB
testcase_61 AC 442 ms
26,916 KB
testcase_62 AC 456 ms
30,924 KB
testcase_63 AC 443 ms
28,612 KB
testcase_64 AC 322 ms
25,544 KB
testcase_65 AC 128 ms
17,188 KB
testcase_66 AC 175 ms
18,856 KB
testcase_67 AC 193 ms
17,980 KB
testcase_68 AC 414 ms
30,688 KB
testcase_69 AC 310 ms
22,864 KB
testcase_70 AC 400 ms
27,676 KB
testcase_71 AC 87 ms
15,448 KB
testcase_72 AC 246 ms
21,832 KB
testcase_73 AC 426 ms
25,528 KB
testcase_74 AC 420 ms
26,204 KB
testcase_75 AC 10 ms
11,620 KB
testcase_76 AC 9 ms
11,756 KB
testcase_77 AC 155 ms
23,732 KB
testcase_78 AC 217 ms
25,588 KB
testcase_79 AC 9 ms
8,752 KB
testcase_80 AC 13 ms
9,772 KB
testcase_81 AC 16 ms
14,388 KB
testcase_82 AC 21 ms
15,036 KB
testcase_83 AC 128 ms
21,036 KB
61_evil_bias_nocross_01.txt AC 140 ms
23,288 KB
61_evil_bias_nocross_02.txt AC 131 ms
22,440 KB
61_evil_bias_nocross_03.txt AC 51 ms
14,860 KB
61_evil_bias_nocross_04.txt AC 141 ms
19,960 KB
61_evil_bias_nocross_05.txt AC 153 ms
22,960 KB
61_evil_bias_nocross_06.txt AC 152 ms
22,376 KB
61_evil_bias_nocross_07.txt AC 85 ms
15,224 KB
61_evil_bias_nocross_08.txt AC 93 ms
21,672 KB
61_evil_bias_nocross_09.txt AC 98 ms
23,344 KB
61_evil_bias_nocross_10.txt AC 65 ms
13,940 KB
61_evil_bias_nocross_11.txt AC 110 ms
19,144 KB
61_evil_bias_nocross_12.txt AC 150 ms
20,760 KB
権限があれば一括ダウンロードができます

ソースコード

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