Submission #1326971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326971		boclobanchat	Flooding Wall (BOI24_wall)	C++20	100 / 100	815 ms	42324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
const long long mod=1e9+7;

inline void add (int &a, int b){
    a += b; if (a >= mod) a -= mod;
}

inline void add_ll (long long &a, int b){
    a += b; if (a >= mod) a -= mod;
}

pair<int,int> val[MAXN],P[MAXN],A[MAXN],seg[MAXN*4];
long long pw[MAXN];
int F[MAXN],suff[MAXN];
pair<int,int> operator+(const pair<int,int>& a,const pair<int,int>& b)
{
	return {(pw[a.second]*b.first+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)>>1;
	build(l,mid,pos<<1);
	build(mid+1,r,pos<<1|1);
}
void update(int i,long long val,int p)
{
	seg[i=F[i]]={val,p};
	while(i >>= 1) seg[i]=seg[i<<1]+seg[i<<1|1];
}
pair<int,int> get(int n,int i)
{
	pair<int,int> ans={0,0};
	int l=0,r=n,pos=1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(mid<=i) ans=ans+seg[pos<<1],pos=pos<<1|1,l=mid+1;
		else pos=pos<<1,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<<1},val[++cnt]={A[i].second,i<<1|1};
	}
	sort(val+1,val+cnt+1);
	for(int i=1;i<=cnt;i++) if(val[i].second & 1) P[val[i].second >> 1].second=i;
	else P[val[i].second >> 1].first=i;
	long long ans=0;
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1], add_ll(pw[i],pw[i-1]);
	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)*pw[n-i])%mod;
	}
	ans=(ans-(seg[1].first-get(cnt,mx-1).first+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-pw[n-1]*(A[i].first+A[i].second)%mod+mod)%mod;
		ans=(ans+(seg[1].first-get(cnt,suff[i]-1).first+mod)*pw[i-1])%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