제출 #1326977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326977		boclobanchat	Flooding Wall (BOI24_wall)	C++20	100 / 100	465 ms	37696 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=(1<<20)+5;
const long long mod=1e9+7;
pair<int,int> val[MAXN],P[MAXN],A[MAXN],seg[MAXN*2];
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};
}
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,long long val,int p)
{
	seg[i+=(1<<20)]={val,p};
	while(i/=2) seg[i]=seg[i*2]+seg[i*2+1];
}
pair<int,int> get(int i)
{
	i++;
	pair<int,int> ans={0,0};
	while(i)
	{
		int p=getlog(i&-i);
		ans=seg[(1<<(20-p))+(i>>p)-1]+ans,i-=i&-i;
	}
	return ans;
}
int fastinput()
{
	char res=' ';
	int ans=0;
	while(!(res>='0'&&res<='9')) res=getchar();
	while(res>='0'&&res<='9') ans=ans*10+res-'0',res=getchar();
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n=fastinput(),cnt=0,mx=0;
	for(int i=1;i<=n;i++) A[i].first=fastinput();
	for(int i=1;i<=n;i++)
	{
		A[i].second=fastinput();
		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;
	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(mx-1).first+mod)*pw[n-i])%mod;
	}
	ans=(ans-(seg[1].first-get(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-(A[i].first+A[i].second)%mod*pw[n-1]%mod+mod)%mod;
		ans=(ans+(seg[1].first-get(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