Submission #1348083

#TimeUsernameProblemLanguageResultExecution timeMemory
1348083PieArmyFlooding Wall (BOI24_wall)C++20
58 / 100
5093 ms14292 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,m=0;
int arr[500023],brr[500023];
pair<int,int>loc[500023];
int val[1000023];
vector<int>v[1000023];
int iki[500023];
int ans=0;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	map<int,int>mp;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		mp[arr[i]]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>brr[i];
		mp[brr[i]]=0;
		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(auto&[a,b]:mp){
		b=++m;
		val[m]=a;
	}
	for(int i=1;i<=n;i++){
		loc[i].fr=mp[arr[i]];
		loc[i].sc=mp[brr[i]];
		v[loc[i].fr].pb(i);
		v[loc[i].sc].pb(i);
	}
	for(int i=1;i<=n;i++){
		int bos=n;
		int sag=0,sol=0;
		for(int j=m;j>=1;j--){
			if(loc[i].fr==j)bos--;
			if(loc[i].sc==j)break;
			for(int x:v[j]){
				if(x==i)continue;
				if(x<i){
					if(sol!=-1){
						if(j==loc[x].fr){
							bos--;
							sol++;
						}
						if(j==loc[x].sc){
							bos+=sol;
							sol=-1;
						}
					}
				}
				else{
					if(sag!=-1){
						if(j==loc[x].fr){
							bos--;
							sag++;
						}
						if(j==loc[x].sc){
							bos+=sag;
							sag=-1;
						}
					}
				}
			}
			//cerr<<i<<"*"<<j<<": "<<bos<<" "<<me<<" "<<sol<<" "<<sag<<endl;
			ans=sum(ans,mul(val[j]-val[j-1],mul(iki[bos],mul(sol==-1?1:sub(iki[sol],1),sag==-1?1:sub(iki[sag],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...