Submission #1215353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215353		boclobanchat	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	26 ms	4164 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long mod=1e9+7;
long long A[MAXN],B[MAXN],pos[MAXN],dsu[MAXN],sum=0;
bool ck[MAXN];
bool comp(int a,int b) { return A[a]>A[b]; }
int root(int i)
{
	if(!dsu[i]) return i;
	return dsu[i]=root(dsu[i]);
}
void merge(int i,int j)
{
	if((i=root(i))==(j=root(j))) return ;
	sum=(sum-B[i]*(B[i]+1)/2%mod+mod)%mod;
	sum=(sum-B[j]*(B[j]+1)/2%mod+mod)%mod;
	dsu[j]=i,B[i]=(B[i]+B[j])%mod;
	sum=(sum+B[i]*(B[i]+1)/2%mod+mod)%mod;
}
long long f(long long n) { return n*(n+1)/2%mod; }
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	stack<int> st;
	long long ans=0;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=n;i++) cin>>B[i];
	for(int i=1;i<=n;i++) pos[i]=i;
	sort(pos+1,pos+n+1,comp);
	for(int i=1;i<=n;i++)
	{
		sum=(sum+B[pos[i]]*(B[pos[i]]+1)/2%mod)%mod,ck[pos[i]]=true;
		if(ck[pos[i]-1]) merge(pos[i],pos[i]-1);
		if(ck[pos[i]+1]) merge(pos[i],pos[i]+1);
		ans=(ans+sum*(f(A[pos[i]])-f(A[pos[i+1]])+mod)%mod)%mod;
	}
	cout<<ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27