Submission #1326951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326951		boclobanchat	Flooding Wall (BOI24_wall)	C++20	100 / 100	605 ms	58728 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const long long mod=1e9+7;
pair<int,int> val[MAXN],P[MAXN],A[MAXN];
long long pref[MAXN],pw[MAXN];
pair<long long,long long> seg[MAXN*4];
int F[MAXN],suff[MAXN];
pair<long long,long long> operator+(const pair<long long,long long>& a,const pair<long long,long long>& b)
{
	return {(b.first*pw[a.second]+a.first)%mod,a.second+b.second};
}
void build(int l,int r,int pos)
{
	seg[pos]={0,0};
	if(l==r)
	{
		F[l]=pos;
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
}
void update(int i,long long val,int p)
{
	seg[i=F[i]]={val,p};
	while(i/=2) seg[i]=seg[i*2]+seg[i*2+1];
}
pair<long long,long long> get(int n,int i)
{
	if(i==n) return seg[1];
	pair<long long,long long> ans={0,0};
	int l=0,r=n,pos=1;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(mid<=i) ans=ans+seg[pos*2],pos=pos*2+1,l=mid+1;
		else pos*=2,r=mid;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,cnt=0,mx=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i].first;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].second;
		if(A[i].first>A[i].second) swap(A[i].first,A[i].second);
		val[++cnt]={A[i].first,i*2},val[++cnt]={A[i].second,i*2+1};
	}
	sort(val+1,val+cnt+1);
	for(int i=1;i<=cnt;i++) if(val[i].second%2) P[val[i].second/2].second=i;
	else P[val[i].second/2].first=i;
	long long ans=0;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
	build(0,cnt,1);
	for(int i=1;i<=n;i++)
	{
		mx=max(mx,P[i].first);
		update(P[i].first,A[i].first,0);
		update(P[i].second,A[i].second,1);
		ans=(ans+(seg[1].first-get(cnt,mx-1).first+mod)%mod*pw[n-i]%mod)%mod;
	}
	ans=(ans-(seg[1].first-get(cnt,mx-1).first+mod)%mod*n%mod+mod)%mod;
	for(int i=n;i;i--) suff[i]=max(suff[i+1],P[i].first);
	for(int i=1;i<=n;i++)
	{
		ans=(ans-(A[i].first+A[i].second)%mod*pw[n-1]%mod+mod)%mod;
		ans=(ans+(seg[1].first-get(cnt,suff[i]-1).first+mod)%mod*pw[i-1]%mod)%mod;
		update(P[i].first,0,0);
		update(P[i].second,0,0);
	}
	cout<<ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30