제출 #1348097

#제출 시각아이디문제언어결과실행 시간메모리
1348097PieArmyFlooding Wall (BOI24_wall)C++20
12 / 100
30 ms10092 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

const int mod=1e9+7;

int sum(int x,int y){
	if(x+y<mod)return x+y;
	return x+y-mod;
}

int sub(int x,int y){
	if(x-y<0)return x-y+mod;
	return x-y;
}

int mul(ll x,ll y){
	return x*y%mod;
}

int n;
int arr[500023],brr[500023];
int iki[500023];
int pref[500023],suf[500023];
int ans=0;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++){
		cin>>brr[i];
		if(brr[i]>arr[i])swap(arr[i],brr[i]);
	}
	iki[0]=1;
	for(int i=1;i<=n;i++){
		iki[i]=mul(iki[i-1],2);
	}
	for(int i=1;i<=n;i++){
		if(arr[i]==1){
			pref[i]=mul(pref[i-1],2);
		}
		else if(brr[i]==1){
			pref[i]=sum(pref[i-1],iki[i-1]);
		}
		else{
			pref[i]=iki[i];
		}
	}
	for(int i=n;i>=1;i--){
		if(arr[i]==1){
			suf[i]=mul(suf[i+1],2);
		}
		else if(brr[i]==1){
			suf[i]=sum(suf[i+1],iki[n-i]);
		}
		else{
			suf[i]=iki[n-i+1];
		}
	}
	for(int i=1;i<=n;i++){
		if(arr[i]==1)ans=sum(ans,mul(pref[i-1],suf[i+1]));
		if(brr[i]==1)ans=sum(ans,mul(pref[i-1],suf[i+1]));
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...