結果

問題 No.2160 みたりのDominator
コンテスト
ユーザー 华恋~韵
提出日時 2024-04-14 10:38:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 3,698 bytes
コンパイル時間 1,093 ms
コンパイル使用メモリ 94,452 KB
実行使用メモリ 30,284 KB
最終ジャッジ日時 2024-10-03 07:35:30
合計ジャッジ時間 7,201 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 93
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#include<array>
#include<assert.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n'
#define DE(fmt,...) fprintf(stderr, "Line %d : " fmt "\n",__LINE__,##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef pair<int,ll>pil;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
template<typename T>T cmin(T &x, T y){return x=x<y?x:y;}
template<typename T>
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
const int N=8000010;
int n1,n2,n3,m,S,T;
array<int,2>eg[N];
void solve(int *s,int l,int r){
	auto pos=[&](int x){
		if(x==S)return 0;
		if(x==T)return r-l+2;
		if(x>=l&&x<=r)
			return x-l+1;
		return -1;
	};
	for(int i=1;i<=m;i++){
		int u=eg[i][0],v=eg[i][1];
		u=pos(u);v=pos(v);
		if(u!=-1&&v!=-1){
			if(u>v)swap(u,v);
			s[u+1]++;s[v+1]--;
		}
	}
	for(int i=1;i<=r-l+2;i++)s[i]+=s[i-1];
	for(int i=1;i<=r-l+2;i++)s[i]=(s[i]>0)?0:1;
	for(int i=1;i<=r-l+2;i++)s[i]+=s[i-1];
}
int s1[N],s2[N],s3[N];
int pre12[N],suf12[N];
int pre13[N],suf13[N];
int pre23[N],suf23[N];
int pre32[N],suf32[N];
void solve(int *pre,int *suf,int l1,int r1,int l2,int r2){
	for(int i=1;i<=r1-l1+2;i++)suf[i]=r2-l2+2,pre[i]=1;
	for(int i=1;i<=m;i++){
		int u=eg[i][0],v=eg[i][1];
		if(v>=l1&&v<=r1)swap(u,v);
		if(u>=l1&&u<=r1&&v>=l2&&v<=r2){
			u=u-l1+1;v=v-l2+1;
			cmin(suf[u],v);
			cmax(pre[u+1],v+1);
		}
	}
	for(int i=2;i<=r1-l1+2;i++)cmax(pre[i],pre[i-1]);
	for(int i=r1-l1+1;i>=1;i--)cmin(suf[i],suf[i+1]);
}
void init(){
	int l1=1,r1=n1;
	int l2=n1+1,r2=n1+n2;
	int l3=n1+n2+1,r3=n1+n2+n3;
	solve(s1,l1,r1);
	solve(s2,l2,r2);
	solve(s3,l3,r3);
	solve(pre12,suf12,l1,r1,l2,r2);
	solve(pre13,suf13,l1,r1,l3,r3);
	solve(pre23,suf23,l2,r2,l3,r3);
	solve(pre32,suf32,l3,r3,l2,r2);
	int L2=1,R2=0;
	int L3=1,R3=0;
	ll ans=0,sum=0;
	auto ins2=[&](int x){
		if(x>=L2&&s2[x]-s2[x-1]){
			int l=max(L3,pre23[x]),r=min(R3,suf23[x]);
			if(l<=r)
				sum+=s3[r]-s3[l-1];
		}
	};
	auto del2=[&](int x){
		if(x<=R2&&s2[x]-s2[x-1]){
			int l=max(L3,pre23[x]),r=min(R3,suf23[x]);
			if(l<=r)
				sum-=s3[r]-s3[l-1];
		}
	};
	auto ins3=[&](int x){
		if(x>=L3&&s3[x]-s3[x-1]){
			int l=max(L2,pre32[x]),r=min(R2,suf32[x]);
			if(l<=r)
				sum+=s2[r]-s2[l-1];
		}
	};
	auto del3=[&](int x){
		if(x<=R3&&s3[x]-s3[x-1]){
			int l=max(L2,pre32[x]),r=min(R2,suf32[x]);
			if(l<=r)
				sum-=s2[r]-s2[l-1];
		}
	};
	for(int o=1;o<=n1+1;o++)if(s1[o]-s1[o-1]){
		while(R2<suf12[o])++R2,ins2(R2);
		while(L2<pre12[o])del2(L2),++L2;
		while(R3<suf13[o])++R3,ins3(R3);
		while(L3<pre13[o])del3(L3),++L3;
		ans+=sum;
	}
	cout<<ans<<'\n';
}
signed main(){
//	#ifdef do_while_true
//		assert(freopen("night.in","r",stdin));
//		assert(freopen("night.out","w",stdout));
//	#endif
	read(n1,n2,n3,m);S=n1+n2+n3+1,T=S+1;
	for(int i=1,u,v;i<=m;i++){
		read(u,v);
		if(u>v)swap(u,v);
		eg[i]={u,v};
		if(u==S&&v==T){
			puts("0");
			return 0;
		}
	}
	init();
    #ifdef do_while_true
//		cerr<<'\n'<<"Time:"<<1.0*clock()/CLOCKS_PER_SEC*1000<<" ms"<<'\n';
	#endif
	return 0;
}
0