#972258 (C++14) No.2160 みたりのDominator

提出ソース

結果

問題	No.2160 みたりのDominator
ユーザー	华恋~韵
提出日時	2024-04-14 11:17:24
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	15 ms 11,264 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	3 ms 5,248 KB
testcase_04	AC	3 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	3 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	3 ms 5,248 KB
testcase_15	AC	3 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	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	4 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	3 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 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	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	12 ms 10,624 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	3 ms 5,248 KB
testcase_39	AC	2 ms 5,248 KB
testcase_40	AC	59 ms 16,896 KB
testcase_41	AC	57 ms 16,768 KB
testcase_42	AC	34 ms 11,136 KB
testcase_43	AC	45 ms 14,464 KB
testcase_44	AC	57 ms 16,640 KB
testcase_45	AC	51 ms 16,256 KB
testcase_46	AC	45 ms 15,744 KB
testcase_47	AC	24 ms 10,240 KB
testcase_48	AC	29 ms 12,928 KB
testcase_49	AC	30 ms 14,208 KB
testcase_50	AC	24 ms 14,208 KB
testcase_51	AC	39 ms 11,776 KB
testcase_52	AC	52 ms 15,872 KB
testcase_53	AC	56 ms 16,384 KB
testcase_54	AC	34 ms 10,752 KB
testcase_55	AC	44 ms 9,344 KB
testcase_56	AC	39 ms 8,704 KB
testcase_57	AC	37 ms 8,576 KB
testcase_58	AC	44 ms 10,752 KB
testcase_59	AC	39 ms 8,832 KB
testcase_60	AC	35 ms 11,520 KB
testcase_61	AC	37 ms 8,960 KB
testcase_62	AC	45 ms 11,648 KB
testcase_63	AC	44 ms 9,856 KB
testcase_64	AC	32 ms 9,344 KB
testcase_65	AC	20 ms 9,216 KB
testcase_66	AC	22 ms 8,320 KB
testcase_67	AC	24 ms 8,704 KB
testcase_68	AC	41 ms 11,264 KB
testcase_69	AC	29 ms 9,088 KB
testcase_70	AC	43 ms 12,160 KB
testcase_71	AC	16 ms 8,960 KB
testcase_72	AC	31 ms 13,312 KB
testcase_73	AC	43 ms 9,600 KB
testcase_74	AC	40 ms 9,088 KB
testcase_75	AC	9 ms 8,576 KB
testcase_76	AC	7 ms 7,808 KB
testcase_77	AC	24 ms 12,032 KB
testcase_78	AC	30 ms 12,672 KB
testcase_79	AC	6 ms 6,144 KB
testcase_80	AC	7 ms 7,040 KB
testcase_81	AC	9 ms 8,960 KB
testcase_82	AC	10 ms 9,856 KB
testcase_83	AC	48 ms 15,232 KB
61_evil_bias_nocross_01.txt	AC	56 ms 16,768 KB
61_evil_bias_nocross_02.txt	AC	66 ms 16,896 KB
61_evil_bias_nocross_03.txt	AC	23 ms 9,856 KB
61_evil_bias_nocross_04.txt	AC	45 ms 10,624 KB
61_evil_bias_nocross_05.txt	AC	50 ms 14,464 KB
61_evil_bias_nocross_06.txt	AC	68 ms 16,128 KB
61_evil_bias_nocross_07.txt	AC	37 ms 11,904 KB
61_evil_bias_nocross_08.txt	AC	54 ms 15,872 KB
61_evil_bias_nocross_09.txt	AC	37 ms 14,336 KB
61_evil_bias_nocross_10.txt	AC	26 ms 8,960 KB
61_evil_bias_nocross_11.txt	AC	37 ms 12,544 KB
61_evil_bias_nocross_12.txt	AC	54 ms 14,720 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード