結果

問題 No.2160 みたりのDominator
ユーザー KudeKude
提出日時 2022-12-11 17:52:44
言語 C++17
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 45 ms
20,580 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 2 ms
5,248 KB
testcase_30 AC 2 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 37 ms
30,920 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 2 ms
5,248 KB
testcase_40 AC 152 ms
22,736 KB
testcase_41 AC 135 ms
21,908 KB
testcase_42 AC 81 ms
14,180 KB
testcase_43 AC 121 ms
19,528 KB
testcase_44 AC 149 ms
22,324 KB
testcase_45 AC 131 ms
21,836 KB
testcase_46 AC 107 ms
20,372 KB
testcase_47 AC 57 ms
12,788 KB
testcase_48 AC 77 ms
17,456 KB
testcase_49 AC 83 ms
19,148 KB
testcase_50 AC 65 ms
18,492 KB
testcase_51 AC 89 ms
14,964 KB
testcase_52 AC 126 ms
21,020 KB
testcase_53 AC 146 ms
22,220 KB
testcase_54 AC 80 ms
13,936 KB
testcase_55 AC 436 ms
27,272 KB
testcase_56 AC 346 ms
23,068 KB
testcase_57 AC 389 ms
24,680 KB
testcase_58 AC 436 ms
29,252 KB
testcase_59 AC 418 ms
25,812 KB
testcase_60 AC 340 ms
28,384 KB
testcase_61 AC 424 ms
26,904 KB
testcase_62 AC 447 ms
30,928 KB
testcase_63 AC 418 ms
28,484 KB
testcase_64 AC 318 ms
25,416 KB
testcase_65 AC 124 ms
17,188 KB
testcase_66 AC 170 ms
18,836 KB
testcase_67 AC 191 ms
17,852 KB
testcase_68 AC 401 ms
30,700 KB
testcase_69 AC 259 ms
22,844 KB
testcase_70 AC 372 ms
27,648 KB
testcase_71 AC 85 ms
15,452 KB
testcase_72 AC 236 ms
21,848 KB
testcase_73 AC 407 ms
25,404 KB
testcase_74 AC 405 ms
26,080 KB
testcase_75 AC 10 ms
11,504 KB
testcase_76 AC 10 ms
11,760 KB
testcase_77 AC 152 ms
23,732 KB
testcase_78 AC 213 ms
25,512 KB
testcase_79 AC 10 ms
8,620 KB
testcase_80 AC 13 ms
9,656 KB
testcase_81 AC 17 ms
14,392 KB
testcase_82 AC 22 ms
15,028 KB
testcase_83 AC 124 ms
20,912 KB
61_evil_bias_nocross_01.txt AC 140 ms
23,252 KB
61_evil_bias_nocross_02.txt AC 130 ms
22,320 KB
61_evil_bias_nocross_03.txt AC 52 ms
14,864 KB
61_evil_bias_nocross_04.txt AC 139 ms
19,960 KB
61_evil_bias_nocross_05.txt AC 149 ms
22,956 KB
61_evil_bias_nocross_06.txt AC 150 ms
22,376 KB
61_evil_bias_nocross_07.txt AC 83 ms
15,224 KB
61_evil_bias_nocross_08.txt AC 92 ms
21,676 KB
61_evil_bias_nocross_09.txt AC 96 ms
23,340 KB
61_evil_bias_nocross_10.txt AC 64 ms
13,868 KB
61_evil_bias_nocross_11.txt AC 112 ms
19,144 KB
61_evil_bias_nocross_12.txt AC 150 ms
20,768 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