結果

問題 No.2160 みたりのDominator
ユーザー 华恋~韵
提出日時 2024-04-14 11:17:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 3,530 bytes
コンパイル時間 1,848 ms
コンパイル使用メモリ 175,004 KB
実行使用メモリ 16,896 KB
最終ジャッジ日時 2024-10-03 08:10:50
合計ジャッジ時間 7,253 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 93
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	char c;
	while(c=getchar())if(c>='0'&&c<='9')break;
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x;
}
const int N=8000006,M=2700005;
int n1,n2,n3,m,cf[3][N],min1[N][2],max1[N][2],num,suf[2][N],tag[M<<2],S,T,N1,N2,N3,ID=3;
long long tr[M<<2];
inline void add(int op,int l,int r){
	++cf[op][l],--cf[op][r+1];
}
struct line{
	int x,y1,y2,v;
}L[N<<1];
inline bool cmp(line x,line y){
	return x.x<y.x;
}
inline void pushdown(int k,int l,int r){
    if(tag[k]){
        int mid=(l+r)>>1;
        tag[k<<1]+=tag[k],tag[k<<1|1]+=tag[k];
        tr[k<<1]+=1ll*tag[k]*(cf[2][mid+n2]-cf[2][l-1+n2]),tr[k<<1|1]+=1ll*tag[k]*(cf[2][r+n2]-cf[2][mid+n2]);
        tag[k]=0;
    }
}
inline void update(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y){
		++tag[k],tr[k]+=cf[2][r+n2]-cf[2][l-1+n2];
		return;
	}
    pushdown(k,l,r);
	int mid=(l+r)>>1;
	if(x<=mid)update(k<<1,l,mid,x,y);
	if(y>=mid+1)update(k<<1|1,mid+1,r,x,y); 
    tr[k]=tr[k<<1]+tr[k<<1|1];
}
inline long long query(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y)return tr[k];
    pushdown(k,l,r);
	long long ans=0;
	int mid=(l+r)>>1;
	if(x<=mid)ans+=query(k<<1,l,mid,x,y);
    if(y>=mid+1)ans+=query(k<<1|1,mid+1,r,x,y);
	return ans; 
}
inline int calc(int x){
    if(x>n3)return x;
    if(ID==3)return x;
    if(ID==1){
        if(x<=N1)return N3+N2+x;
        if(x<=N1+N2)return x-N1+N3;
        return x-N1-N2;
    }
    if(x<=N1)return x;
    if(x<=N1+N2)return x+N3;
    return x-N2;
}
int main(){
	n1=read(),n2=read(),n3=read(),m=read();
    N1=n1,N2=n2,N3=n3;
    if(n1<n2&&n1<n3)ID=1,swap(n1,n3);
    else if(n2<n3)ID=2,swap(n2,n3);
	n2+=n1;
	n3+=n2;
	S=n3+1;
	T=S+1;
	int x,y;
	for(int i=1;i<=n1;++i)min1[i][0]=min1[i][1]=T;
	for(int i=n1+1;i<=n2;++i)min1[i][0]=T;
	while(m--){
		x=calc(read()),y=calc(read());
		if(x>y)swap(x,y);
		if(y==T){
			if(x==S){
				cout<<0;
				return 0;
			}
			if(x<=n1)add(0,x+1,n1+1);
			else if(x<=n2)add(1,x+1,n2+1);
			else add(2,x+1,n3+1);
		}
		else if(y==S){
			if(x<=n1)add(0,1,x);
			else if(x<=n2)add(1,n1+1,x);
			else add(2,n2+1,x);
		}
		else{
			if(y<=n1)add(0,x+1,y);
			else if(y<=n2){
				if(x<=n1){
					min1[x][0]=min(min1[x][0],y);
					max1[x][0]=max(max1[x][0],y);
				}
				else add(1,x+1,y);
			}
			else{
				if(x<=n1){
					min1[x][1]=min(min1[x][1],y);
					max1[x][1]=max(max1[x][1],y);
				}
				else if(x<=n2){
					min1[x][0]=min(min1[x][0],y);
					max1[x][0]=max(max1[x][0],y);
				}
				else add(2,x+1,y);
			}
		}
	}
	for(int i=0;i<=2;++i){
		for(int j=1;j<=n3+1;++j)cf[i][j]+=cf[i][j-1];
	}
	suf[0][n1+1]=n2+1,suf[1][n1+1]=n3+1;
	for(int i=n1;i;--i)suf[0][i]=min(suf[0][i+1],min1[i][0]),suf[1][i]=min(suf[1][i+1],min1[i][1]);
	int pre0=n1+1,pre1=n2+1;
	for(int i=1;i<=n1+1;++i){
		if(i!=1)pre0=max(pre0,max1[i-1][0]+1),pre1=max(pre1,max1[i-1][1]+1);
		if(!cf[0][i]&&pre0<=suf[0][i]&&pre1<=suf[1][i]){
			L[++num]={suf[0][i],pre1,suf[1][i],1};
			if(pre0!=n1+1)L[++num]={pre0-1,pre1,suf[1][i],-1};
		}
	}
	sort(L+1,L+num+1,cmp);
	pre0=n2+1,suf[0][n2+1]=n3+1;
    for(int i=n2;i>n1;--i)suf[0][i]=min(suf[0][i+1],min1[i][0]);
	for(int i=n2+1;i<=n3+1;++i)cf[2][i]=cf[2][i-1]+(cf[2][i]==0);
	int now=0;
	long long ans=0;
	for(int i=n1+1;i<=n2+1;++i){
		if(i!=n1+1)pre0=max(pre0,max1[i-1][0]+1);
		if(!cf[1][i]&&pre0<=suf[0][i])update(1,1,n3-n2+1,pre0-n2,suf[0][i]-n2);
		while(now+1<=num&&L[now+1].x==i){
			++now;
			ans+=1ll*L[now].v*query(1,1,n3-n2+1,L[now].y1-n2,L[now].y2-n2);
		}
	} 
	cout<<ans;
}
0