제출 #1348766

#제출 시각아이디문제언어결과실행 시간메모리
1348766PieArmyFlooding Wall (BOI24_wall)C++20
100 / 100
4922 ms184320 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 fpow(int x,int y=mod-2){
	int res=1;
	while(y>0){
		if(y&1)res=mul(res,x);
		x=mul(x,x);
		y>>=1;
	}
	return res;
}

const int k=6;
typedef array<int,k> ar;

int iki[500023],ik[500023];

ar comb(ar a,ar b){
	ar res;
	res[1]=a[1]+b[1];
	res[2]=a[2]+b[2];
	res[3]=sum(sum(mul(a[3],iki[b[1]]),b[3]),mul(mul(iki[b[1]],ik[a[1]]),b[5]));
	res[4]=sum(sum(mul(a[4],iki[b[2]]),b[4]),mul(mul(iki[b[2]],ik[a[2]]),b[5]));
	res[5]=a[5]+b[5];
	res[0]=sum(mul(a[0],iki[b[1]+b[2]]),b[0]);
	res[0]=sum(res[0],mul(ik[a[1]],mul(iki[b[1]],b[4])));
	res[0]=sum(res[0],mul(ik[a[2]],mul(iki[b[2]],b[3])));
	res[0]=sum(res[0],mul(mul(ik[a[1]],ik[a[2]]),mul(iki[b[1]+b[2]],b[5])));
	return res;
}

struct Seg{
	int n;
	vector<int>arr;
	vector<ar>tree;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]={0,0,0,0,0,arr[left]};
			return;
		}
		build(node*2,left,mid);
		build(node*2+1,mid+1,right);
		tree[node]=comb(tree[node*2],tree[node*2+1]);
	}
	void init(vector<int>Arr){
		arr=Arr;
		n=arr.size();
		tree.clear();
		tree.resize(n<<2);
		build();
	}
	int l,r,x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node][r]+=x;
			tree[node][0]=mul(tree[node][5],mul(ik[tree[node][1]],ik[tree[node][2]]));
			tree[node][3]=mul(tree[node][5],ik[tree[node][1]]);
			tree[node][4]=mul(tree[node][5],ik[tree[node][2]]);
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=comb(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int tar2,int val){
		l=tar;r=tar2;x=val;
		up();
	}
	ar qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return {0,0,0,0,0,0};
		return comb(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	ar query(int left,int right){
		l=left;r=right;
		if(l>r)return {0,0,0,0,0,0};
		return qu();
	}
};

int n,m;
int arr[500023],brr[500023];
int val[1000023];
pair<int,int>loc[500023];
Seg seg;
map<int,int,greater<int>>mp;
multiset<int>ls,rs;
int ans=0;

void add(int tar,int t){
	seg.update(loc[tar].sc,t,1);
	if(t==1){
		ls.insert(loc[tar].fr);
	}
	else{
		rs.insert(loc[tar].fr);
	}
}

void sil(int tar,int t){
	seg.update(loc[tar].sc,t,-1);
	if(t==1){
		ls.erase(ls.find(loc[tar].fr));
	}
	else{
		rs.erase(rs.find(loc[tar].fr));
	}
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	iki[0]=1;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		mp[arr[i]]=0;
		iki[i]=mul(iki[i-1],2);
		ik[i]=sub(iki[i],1);
	}
	for(int i=1;i<=n;i++){
		cin>>brr[i];
		mp[brr[i]]=0;
		if(arr[i]>brr[i])swap(arr[i],brr[i]);
	}
	for(auto&[a,b]:mp){
		val[m]=a;
		b=m++;
	}
	for(int i=1;i<=n;i++){
		loc[i].fr=mp[arr[i]];
		loc[i].sc=mp[brr[i]];
	}
	{
		vector<int>v;
		for(int i=0;i<m;i++){
			v.pb(val[i]-val[i+1]);
		}
		seg.init(v);
	}
	ls.insert(m);
	rs.insert(m);
	for(int i=1;i<=n;i++){
		add(i,2);
	}
	for(int i=1;i<=n;i++){
		ans=sub(ans,mul(iki[n-1],sum(brr[i],arr[i])));
		sil(i,2);
		int x=*ls.begin(),y=*rs.begin();
		ar res=seg.query(0,min(loc[i].fr,min(x,y))-1);
		ans=sum(ans,mul(iki[n-1-res[1]-res[2]],res[0]));
		ans=sum(ans,mul(iki[n-1],val[min(loc[i].fr,max(x,y))]));
		if(loc[i].fr>min(x,y)){
			if(x<y){
				int cnt=res[2];
				res=comb({0,0,cnt,0,0,0},seg.query(x,min(loc[i].fr,y)-1));
				ans=sum(ans,mul(iki[n-1-res[2]],res[4]));
			}
			if(y<x){
				int cnt=res[1];
				res=comb({0,cnt,0,0,0,0},seg.query(y,min(loc[i].fr,x)-1));
				ans=sum(ans,mul(iki[n-1-res[1]],res[3]));
			}
		}
		res=seg.query(0,min(loc[i].sc,min(x,y))-1);
		ans=sum(ans,mul(iki[n-1-res[1]-res[2]],res[0]));
		ans=sum(ans,mul(iki[n-1],val[min(loc[i].sc,max(x,y))]));
		if(loc[i].sc>min(x,y)){
			if(x<y){
				int cnt=res[2];
				res=comb({0,0,cnt,0,0,0},seg.query(x,min(loc[i].sc,y)-1));
				ans=sum(ans,mul(iki[n-1-res[2]],res[4]));
			}
			if(y<x){
				int cnt=res[1];
				res=comb({0,cnt,0,0,0,0},seg.query(y,min(loc[i].sc,x)-1));
				ans=sum(ans,mul(iki[n-1-res[1]],res[3]));
			}
		}
		//cerr<<ans<<endl;
		add(i,1);
	}
	cout<<ans<<endl;
	//cerr<<(float)clock()/CLOCKS_PER_SEC<<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...