結果

問題 No.2160 みたりのDominator
ユーザー 👑 rin204rin204
提出日時 2022-12-11 19:16:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 6,794 bytes
コンパイル時間 2,926 ms
コンパイル使用メモリ 240,784 KB
実行使用メモリ 30,880 KB
最終ジャッジ日時 2024-10-15 15:25:50
合計ジャッジ時間 9,924 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 65 ms
24,296 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 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 1 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 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 1 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 1 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 1 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 1 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 1 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 19 ms
30,880 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 89 ms
23,092 KB
testcase_41 AC 84 ms
22,928 KB
testcase_42 AC 48 ms
14,620 KB
testcase_43 AC 70 ms
19,708 KB
testcase_44 AC 88 ms
22,696 KB
testcase_45 AC 78 ms
22,320 KB
testcase_46 AC 65 ms
21,444 KB
testcase_47 AC 35 ms
13,416 KB
testcase_48 AC 43 ms
18,228 KB
testcase_49 AC 45 ms
20,844 KB
testcase_50 AC 34 ms
21,016 KB
testcase_51 AC 55 ms
15,448 KB
testcase_52 AC 81 ms
21,676 KB
testcase_53 AC 86 ms
22,496 KB
testcase_54 AC 47 ms
14,132 KB
testcase_55 AC 74 ms
19,688 KB
testcase_56 AC 74 ms
16,600 KB
testcase_57 AC 74 ms
16,480 KB
testcase_58 AC 82 ms
21,928 KB
testcase_59 AC 72 ms
18,404 KB
testcase_60 AC 76 ms
24,684 KB
testcase_61 AC 70 ms
14,984 KB
testcase_62 AC 77 ms
22,096 KB
testcase_63 AC 74 ms
19,776 KB
testcase_64 AC 71 ms
17,424 KB
testcase_65 AC 33 ms
16,464 KB
testcase_66 AC 37 ms
14,072 KB
testcase_67 AC 42 ms
13,092 KB
testcase_68 AC 79 ms
20,100 KB
testcase_69 AC 51 ms
16,704 KB
testcase_70 AC 68 ms
17,104 KB
testcase_71 AC 26 ms
15,588 KB
testcase_72 AC 45 ms
15,296 KB
testcase_73 AC 75 ms
19,148 KB
testcase_74 AC 72 ms
18,140 KB
testcase_75 AC 12 ms
15,576 KB
testcase_76 AC 9 ms
12,480 KB
testcase_77 AC 36 ms
18,856 KB
testcase_78 AC 44 ms
19,200 KB
testcase_79 AC 8 ms
9,600 KB
testcase_80 AC 8 ms
10,172 KB
testcase_81 AC 23 ms
17,664 KB
testcase_82 AC 19 ms
17,328 KB
testcase_83 AC 54 ms
20,240 KB
61_evil_bias_nocross_01.txt AC 84 ms
23,368 KB
61_evil_bias_nocross_02.txt AC 91 ms
22,872 KB
61_evil_bias_nocross_03.txt AC 47 ms
14,404 KB
61_evil_bias_nocross_04.txt AC 71 ms
20,264 KB
61_evil_bias_nocross_05.txt AC 85 ms
23,288 KB
61_evil_bias_nocross_06.txt AC 100 ms
23,172 KB
61_evil_bias_nocross_07.txt AC 54 ms
15,852 KB
61_evil_bias_nocross_08.txt AC 86 ms
21,716 KB
61_evil_bias_nocross_09.txt AC 82 ms
23,152 KB
61_evil_bias_nocross_10.txt AC 51 ms
14,552 KB
61_evil_bias_nocross_11.txt AC 64 ms
20,108 KB
61_evil_bias_nocross_12.txt AC 84 ms
21,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;
using namespace atcoder;
using ll = long long;
#define endl '\n'

struct S{
    ll tot;
    ll add;
};

S op(S l, S r){
    return S{l.tot + r.tot, l.add + r.add};
}

S e(){
    return {0, 0};
}

using F = ll;

S mapping(F x, S y){
    return S{y.tot + x * y.add, y.add};
}

F composition(F l, F r){
    return l + r;
}

F id(){
    return 0LL;
}



void solve(){
    int n0, n1, n2, m;
    cin >> n0 >> n1 >> n2 >> m;
    int n = n0 + n1 + n2;
    vector<int> N = {n0, n1, n2};
    vector<vector<int>> imos(3, vector<int>());
    vector<vector<bool>> dub(3, vector<bool>());
    for(int i = 0; i < 3; i++){
        imos[i].assign(N[i] + 2, 0);
        dub[i].assign(N[i] + 2, false);
    }

    auto f=[&](int x) -> pair<int, int> {
        if(x <= n0) return {0, x};
        else if(x <= n0 + n1) return {1, x - n0};
        else if(x <= n) return {2, x - n0 - n1};
        else return {3, x - n - 1};
    };

    vector<vector<vector<pair<int, int>>>> E(3, vector<vector<pair<int, int>>>(3, vector<pair<int, int>>()));

    int u, v;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        auto f1 = f(u);
        auto f2 = f(v);
        if(f1.first == f2.first){
            if(f1.first == 3){
                cout << 0 << endl;
                return;
            }
            if(f1.second > f2.second) swap(f1, f2);
            if(f1.second + 1 == f2.second) dub[f1.first][f1.second] = true;
            imos[f1.first][f1.second]++;
            imos[f1.first][f2.second]--;
        }
        else{
            if(f1.first > f2.first) swap(f1, f2);
            if(f2.first == 3){
                f2.first = f1.first;
                if(f2.second == 1) f2.second = N[f1.first] + 1;
                if(f1.second > f2.second) swap(f1, f2);
                if(f1.second + 1 == f2.second) dub[f1.first][f1.second] = true;
                imos[f1.first][f1.second]++;
                imos[f1.first][f2.second]--;
            }
            else{
                E[f1.first][f2.first].push_back({f1.second, f2.second});
                E[f2.first][f1.first].push_back({f2.second, f1.second});
            }
        }
    }

    vector<vector<int>> B(3, vector<int>());
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < N[i] + 1; j++){
            if(imos[i][j] == 0 && !dub[i][j]) B[i].push_back(j);
            imos[i][j + 1] += imos[i][j];
        }
    }

    auto LR=[&](int i, int j)-> pair<vector<int>, vector<int>> {
        vector<int> L(N[i] + 2, 0), R(N[i] + 2, N[j] + 1), ret(N[i] + 1);
        for(auto tmp:E[i][j]){
            int p1 = tmp.first;
            int p2 = tmp.second;
            L[p1] = max(L[p1], p2);
            R[p1] = min(R[p1], p2);
        }
        for(int k = 1; k < N[i] + 2; k++) L[k] = max(L[k], L[k - 1]);
        for(int k = N[i]; k >= 0; k--) R[k] = min(R[k], R[k + 1]);
        return {L, R};
        /*
        for(int k = 0; k < N[i] + 1; k++){
            auto itl = lower_bound(B[j].begin(), B[j].end(), L[k]);
            auto itr = lower_bound(B[j].begin(), B[j].end(), R[k + 1]);
            ret[k] = max(0, int(itr - itl));
        }

        return ret;
        */
    };

    auto ok=[&](int i, int j){
        return (imos[i][j] == 0) && (!dub[i][j]);
    };

    auto tmp1 = LR(0, 1);
    auto tmp2 = LR(0, 2);
    vector<pair<pair<int, int>, pair<int, int>>> Q;
    for(int k = 0; k < N[0] + 1; k++){
        if(ok(0, k) && tmp1.first[k] < tmp1.second[k + 1] && tmp2.first[k] < tmp2.second[k + 1]){
            Q.push_back({{tmp1.first[k], tmp1.second[k + 1]}, {tmp2.first[k], tmp2.second[k + 1]}});
        }
    }

    vector<S> init(N[2] + 1);
    for(int i = 0; i < N[2] + 1; i++){
        init[i] = {0, 0};
        if(ok(2, i)) init[i].add = 1;
    }


    lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);

    auto tmp3 = LR(1, 2);
    ll ans = 0;
    vector<vector<pair<int, int>>> add(N[1] + 1, vector<pair<int, int>>());
    vector<vector<pair<int, int>>> sub(N[1] + 1, vector<pair<int, int>>());
    for(auto tmp:Q){
        add[tmp.first.second - 1].push_back(tmp.second);
        sub[tmp.first.first].push_back(tmp.second);
    }

    for(int i = 0; i < N[1] + 1; i++){
        
        for(auto tmp:sub[i]){
            // cout << "S" << " " << tmp.first << " " << tmp.second << endl;
            ans -= seg.prod(tmp.first, tmp.second).tot;
        }
        if(ok(1, i)){
            if(tmp3.first[i] < tmp3.second[i + 1]){
                seg.apply(tmp3.first[i], tmp3.second[i + 1], 1);
            }
        }
        for(auto tmp:add[i]){
            // cout << "A" << " " << tmp.first << " " << tmp.second << endl;
            ans += seg.prod(tmp.first, tmp.second).tot;
        }
    }
    cout << ans << endl;

    /*
    ll cnt = 0;
    auto tmp3 = LR(1, 2);
    
    for(auto tmp:Q){
        auto p1 = tmp.first;
        auto p2 = tmp.second;
        for(int i = p1.first; i < p1.second ; i++){
            if(!ok(1, i)) continue;
            for(int j = p2.first; j < p2.second; j++){
                if(ok(2, j) && tmp3.first[i] <= j && j < tmp3.second[i + 1]) cnt++;
            }
        }
    }
    cout << cnt << endl;
    */

    /*
    auto f1=[&](int i, int j){
        auto R = LR(i, j);
        ll ret = 0;
        for(int k = 0; k < N[i] + 1; k++){
            if(imos[i][k] == 0 && !dub[i][k]){
                ret += R[k];
            }
        }
        return ret;
    };

    auto f2=[&](int i){
        auto R1 = LR(i, (i + 1) % 3);
        auto R2 = LR(i, (i + 2) % 3);
        ll ret = 0;
        for(int k = 0; k < N[i] + 1; k++){
            if(imos[i][k] == 0 && !dub[i][k]){
                ret += ll(R1[k]) * ll(R2[k]);
            }
        }
        return ret;
    };

    ll ans = ll(B[0].size()) * ll(B[1].size()) * ll(B[2].size());

    for(int i = 0; i < 3; i++){
        // cout << ans << endl;
        ans -= ll(B[i].size()) * f1((i + 1) % 3, (i + 2) % 3);
        // cout << ans << endl;
        ans += f2(i);
    }
    cout << ans << endl;
    */
   
    /*
    ll cnt = 0;
    for(auto i:B[0]){
        for(auto j:B[1]){
            for(auto k:B[2]){
                vector<int> A = {i, j, k};
                bool ok = true;
                for(int t1 = 0; t1 < 2; t1++){
                    for(int t2 = t1 + 1; t2 < 3; t2++){
                        for(auto tmp:E[t1][t2]){
                            int p1 = tmp.first;
                            int p2 = tmp.second;
                            if(bool(A[t1] < p1) ^ (A[t2] < p2)) ok = false;
                        }
                    }
                }
                if(ok) cnt++;
            }
        }
    }
    cout << cnt << endl;
    */
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    solve();
}
0