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

提出ソース

結果

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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 19,928 KB
testcase_01	AC	10 ms 23,492 KB
testcase_02	AC	5 ms 19,928 KB
testcase_03	AC	7 ms 26,056 KB
testcase_04	AC	6 ms 24,016 KB
testcase_05	AC	6 ms 26,056 KB
testcase_06	AC	6 ms 26,060 KB
testcase_07	AC	6 ms 21,972 KB
testcase_08	AC	6 ms 19,928 KB
testcase_09	AC	5 ms 19,928 KB
testcase_10	AC	5 ms 19,928 KB
testcase_11	AC	5 ms 19,800 KB
testcase_12	AC	5 ms 19,928 KB
testcase_13	AC	5 ms 19,804 KB
testcase_14	AC	5 ms 19,924 KB
testcase_15	AC	5 ms 19,928 KB
testcase_16	AC	6 ms 19,928 KB
testcase_17	AC	5 ms 19,928 KB
testcase_18	AC	5 ms 19,928 KB
testcase_19	AC	5 ms 19,924 KB
testcase_20	AC	5 ms 19,924 KB
testcase_21	AC	5 ms 19,796 KB
testcase_22	AC	5 ms 19,928 KB
testcase_23	AC	7 ms 24,012 KB
testcase_24	AC	6 ms 25,928 KB
testcase_25	AC	7 ms 26,056 KB
testcase_26	AC	7 ms 26,060 KB
testcase_27	AC	7 ms 26,056 KB
testcase_28	AC	6 ms 26,064 KB
testcase_29	AC	7 ms 26,056 KB
testcase_30	AC	7 ms 26,064 KB
testcase_31	AC	6 ms 26,060 KB
testcase_32	AC	6 ms 26,060 KB
testcase_33	AC	5 ms 17,876 KB
testcase_34	AC	10 ms 21,296 KB
testcase_35	AC	3 ms 6,820 KB
testcase_36	AC	5 ms 19,924 KB
testcase_37	AC	6 ms 26,060 KB
testcase_38	AC	7 ms 24,016 KB
testcase_39	AC	6 ms 24,012 KB
testcase_40	AC	16 ms 23,328 KB
testcase_41	AC	14 ms 21,268 KB
testcase_42	AC	11 ms 22,688 KB
testcase_43	AC	14 ms 21,008 KB
testcase_44	AC	16 ms 23,296 KB
testcase_45	AC	17 ms 25,380 KB
testcase_46	AC	14 ms 23,316 KB
testcase_47	AC	12 ms 22,676 KB
testcase_48	AC	14 ms 23,060 KB
testcase_49	AC	15 ms 21,248 KB
testcase_50	AC	15 ms 25,376 KB
testcase_51	AC	12 ms 20,784 KB
testcase_52	AC	14 ms 25,280 KB
testcase_53	AC	15 ms 21,232 KB
testcase_54	AC	12 ms 20,784 KB
testcase_55	AC	48 ms 30,284 KB
testcase_56	AC	42 ms 8,064 KB
testcase_57	AC	45 ms 8,064 KB
testcase_58	AC	48 ms 9,600 KB
testcase_59	AC	46 ms 8,704 KB
testcase_60	AC	46 ms 9,728 KB
testcase_61	AC	45 ms 8,832 KB
testcase_62	AC	49 ms 10,112 KB
testcase_63	AC	47 ms 8,704 KB
testcase_64	AC	44 ms 8,576 KB
testcase_65	AC	19 ms 7,040 KB
testcase_66	AC	24 ms 6,656 KB
testcase_67	AC	24 ms 7,040 KB
testcase_68	AC	43 ms 9,856 KB
testcase_69	AC	33 ms 7,808 KB
testcase_70	AC	42 ms 10,240 KB
testcase_71	AC	15 ms 6,528 KB
testcase_72	AC	27 ms 9,472 KB
testcase_73	AC	48 ms 8,576 KB
testcase_74	AC	45 ms 8,576 KB
testcase_75	AC	6 ms 6,272 KB
testcase_76	AC	5 ms 5,504 KB
testcase_77	AC	21 ms 8,576 KB
testcase_78	AC	25 ms 8,960 KB
testcase_79	AC	5 ms 5,248 KB
testcase_80	AC	5 ms 5,248 KB
testcase_81	AC	6 ms 6,656 KB
testcase_82	AC	10 ms 7,680 KB
testcase_83	AC	13 ms 7,168 KB
61_evil_bias_nocross_01.txt	AC	14 ms 7,808 KB
61_evil_bias_nocross_02.txt	AC	13 ms 7,936 KB
61_evil_bias_nocross_03.txt	AC	8 ms 6,016 KB
61_evil_bias_nocross_04.txt	AC	10 ms 6,656 KB
61_evil_bias_nocross_05.txt	AC	13 ms 7,680 KB
61_evil_bias_nocross_06.txt	AC	14 ms 7,808 KB
61_evil_bias_nocross_07.txt	AC	9 ms 6,400 KB
61_evil_bias_nocross_08.txt	AC	12 ms 7,424 KB
61_evil_bias_nocross_09.txt	AC	11 ms 7,680 KB
61_evil_bias_nocross_10.txt	AC	8 ms 5,888 KB
61_evil_bias_nocross_11.txt	AC	10 ms 6,656 KB
61_evil_bias_nocross_12.txt	AC	13 ms 7,168 KB

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

ソースコード

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

yukicoder

結果

テストケース

ソースコード