結果
問題 | No.2160 みたりのDominator |
ユーザー |
👑 |
提出日時 | 2022-12-11 01:33:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,742 bytes |
コンパイル時間 | 1,302 ms |
コンパイル使用メモリ | 116,048 KB |
実行使用メモリ | 18,216 KB |
最終ジャッジ日時 | 2024-10-15 01:27:29 |
合計ジャッジ時間 | 6,886 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 WA * 46 |
ソースコード
#include <cassert>#include <cmath>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using Int = long long;template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i>= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }int N[3], M;vector<int> U, V;int main() {for (; ~scanf("%d%d%d%d", &N[0], &N[1], &N[2], &M); ) {for (int h = 0; h < 3; ++h) {++N[h];}U.resize(M);V.resize(M);for (int m = 0; m < M; ++m) {scanf("%d%d", &U[m], &V[m]);}const int src = (N[0] - 1) + (N[1] - 1) + (N[2] - 1) + 1;const int snk = src + 1;const int offs[3] = {0, (N[0] - 1), (N[0] - 1) + (N[1] - 1)};auto decode = [&](int h, int u) -> int {if (u == src) return 0;if (u == snk) return N[h];u -= offs[h];if (0 < u && u < N[h]) return u;return -1;};vector<pair<int, int>> pss[3][3];for (int m = 0; m < M; ++m) {for (int h0 = 0; h0 < 3; ++h0) for (int h1 = h0; h1 < 3; ++h1) {{const int u = decode(h0, U[m]);const int v = decode(h1, V[m]);if (~u && ~v && (h0 < h1 || u < v)) {pss[h0][h1].emplace_back(u, v);}}{const int u = decode(h0, V[m]);const int v = decode(h1, U[m]);if (~u && ~v && (h0 < h1 || u < v)) {pss[h0][h1].emplace_back(u, v);}}}}// for(int h0=0;h0<3;++h0)for(int h1=h0;h1<3;++h1)cerr<<"pss["<<h0<<"]["<<h1<<"] = "<<pss[h0][h1]<<endl;// (h, h)vector<int> fss[3], gss[3];for (int h = 0; h < 3; ++h) {fss[h].assign(N[h] + 1, 0);for (const auto &p : pss[h][h]) {++fss[h][p.first];--fss[h][p.second];}for (int x = 0; x < N[h]; ++x) {fss[h][x + 1] += fss[h][x];}gss[h].assign(N[h] + 1, 0);for (int x = 0; x < N[h]; ++x) {gss[h][x + 1] = gss[h][x] + ((!fss[h][x]) ? 1 : 0);}// cerr<<"fss["<<h<<"] = "<<fss[h]<<endl;// cerr<<"gss["<<h<<"] = "<<gss[h]<<endl;}vector<int> lsss[3][3], rsss[3][3];for (int h0 = 0; h0 < 3; ++h0) for (int h1 = h0; h1 < 3; ++h1) {lsss[h0][h1].assign(N[h0], 0);rsss[h0][h1].assign(N[h0], N[h1]);for (const auto &p : pss[h0][h1]) {if (0 < p.first) {chmin(rsss[h0][h1][p.first - 1], p.second);}if (p.first < N[h0]) {chmax(lsss[h0][h1][p.first], p.second);}}for (int x = 0; x < N[h0] - 1; ++x) {chmax(lsss[h0][h1][x + 1], lsss[h0][h1][x]);}for (int x = N[h0]; --x >= 1; ) {chmin(rsss[h0][h1][x - 1], rsss[h0][h1][x]);}// cerr<<"lsss["<<h0<<"]["<<h1<<"] = "<<lsss[h0][h1]<<endl;// cerr<<"rsss["<<h0<<"]["<<h1<<"] = "<<rsss[h0][h1]<<endl;}{const int h0 = 2;const int h1 = 1;lsss[h0][h1].assign(N[h0], 0);rsss[h0][h1].assign(N[h0], N[h1]);for (const auto &p : pss[h1][h0]) { // !if (0 < p.second) {chmin(rsss[h0][h1][p.second - 1], p.first);}if (p.second < N[h0]) {chmax(lsss[h0][h1][p.second], p.first);}}for (int x = 0; x < N[h0] - 1; ++x) {chmax(lsss[h0][h1][x + 1], lsss[h0][h1][x]);}for (int x = N[h0]; --x >= 1; ) {chmin(rsss[h0][h1][x - 1], rsss[h0][h1][x]);}// cerr<<"lsss["<<h0<<"]["<<h1<<"] = "<<lsss[h0][h1]<<endl;// cerr<<"rsss["<<h0<<"]["<<h1<<"] = "<<rsss[h0][h1]<<endl;}// (1, 2)vector<int> headss[3];vector<Int> sumss[3];for (int h = 1; h < 3; ++h) {headss[h].assign(N[h] + 1, 0);for (int x = 0; x < N[h]; ++x) {headss[h][x + 1] = (x + 1 < N[h] && lsss[h][h ^ 3][x] == lsss[h][h ^ 3][x + 1]) ? headss[h][x] : (x + 1);}sumss[h].assign(N[h] + 1, 0);for (int x = 0; x < N[h]; ++x) {sumss[h][x + 1] = sumss[h][x];if (!fss[h][x]) {const int l = lsss[h][h ^ 3][x];const int r = rsss[h][h ^ 3][x];if (l < r) {sumss[h][x + 1] += (gss[h ^ 3][r] - gss[h ^ 3][l]);}}}}auto calc = [&](int x1, int x2) -> Int {Int ret = 0;if (x2 == N[2] || x1 < lsss[2][1][x2]) {ret += sumss[1][x1];} else if (x1 == N[1] || x2 < lsss[1][2][x1]) {ret += sumss[2][x2];} else {const int xx1 = headss[1][x1];const int xx2 = headss[2][x2];ret += sumss[1][x1];ret += (Int)(gss[1][x1] - gss[1][xx1]) * (gss[2][x2] - gss[2][xx2]);}// if(N[0]<=10)cerr<<"calc "<<x1<<" "<<x2<<" = "<<ret<<endl;return ret;};Int ans = 0;for (int x0 = 0; x0 < N[0]; ++x0) if (!fss[0][x0]) {if (lsss[0][1][x0] < rsss[0][1][x0] && lsss[0][2][x0] < rsss[0][2][x0]) {ans += calc(lsss[0][1][x0], lsss[0][2][x0]);ans -= calc(lsss[0][1][x0], rsss[0][2][x0]);ans -= calc(rsss[0][1][x0], lsss[0][2][x0]);ans += calc(rsss[0][1][x0], rsss[0][2][x0]);}}printf("%lld\n", ans);#ifdef LOCALif((Int)N[0]*N[1]*N[2]<=1000){Int brt=0;{int xs[3];for(xs[0]=0;xs[0]<N[0];++xs[0])for(xs[1]=0;xs[1]<N[1];++xs[1])for(xs[2]=0;xs[2]<N[2];++xs[2]){if ([&]() -> bool {for(int h0=0;h0<3;++h0)for(int h1=h0;h1<3;++h1){for(const auto &p:pss[h0][h1]){if((xs[h0]<p.first)!=(xs[h1]<p.second))return false;}}return true;}()) {++brt;}}}if(brt!=ans){cerr<<"N = ";pv(N,N+3);cerr<<"U = "<<U<<endl;cerr<<"V = "<<V<<endl;for(int h0=0;h0<3;++h0)for(int h1=h0;h1<3;++h1)cerr<<"pss["<<h0<<"]["<<h1<<"] = "<<pss[h0][h1]<<endl;cerr<<"brt = "<<brt<<", ans = "<<ans<<endl;assert(false);}}#endif}return 0;}