結果
| 問題 | No.2160 みたりのDominator |
| コンテスト | |
| ユーザー |
 rin204
|
| 提出日時 | 2022-12-11 19:16:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 97 ms / 2,000 ms |
| コード長 | 6,794 bytes |
| コンパイル時間 | 3,028 ms |
| コンパイル使用メモリ | 230,492 KB |
| 最終ジャッジ日時 | 2025-02-09 09:42:43 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 93 |
ソースコード
#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();
}