Submission #381002

#	Time	Username	Problem	Language	Result	Execution time	Memory
381002		iris2617	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	92 ms	5612 KiB

fancyfence

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

int H[100010],W[100010];
matsuri st[100010];
int p;

int qwq(int a)
{
	int b,res;
	b=iris-2;
	res=1;
	while(b)
	{
		if(b&1)
			res=res*a%iris;
		a=a*a%iris;
		b>>=1;
	}
	return res;
}

int cal(int h,int w)
{
	int ans,ouo;
	h%=iris;
	w%=iris;
	ans=(w*(w-1+iris)%iris*h%iris*(h-1+iris)%iris)%iris;
	ans=ans*qwq(4)%iris;
	ouo=(w*(w-1)%iris*h%iris+h*(h-1)%iris*w)%iris;
	ouo=ouo*qwq(2)%iris;
	ans=(ans+ouo+h*w)%iris;
	return ans;
}

int ccc(int h,int w1,int w2)
{
	h%=iris;
	w1%=iris;
	w2%=iris;
	int sum1,sum2;
	sum1=w1*w2%iris*h%iris;
	sum2=h*w1%iris*h%iris*w2%iris;
	sum1=((sum2-sum1+iris)%iris*qwq(2)%iris+sum1)%iris;
//	cout<<h<<' '<<w1<<' '<<w2<<' '<<sum1<<'\n';
	return sum1;
}

int stacksum;

void pop()
{
	int h,w,aoi;
	h=st[p-1].first;
	w=st[p-1].second;
	aoi=(h+1)*h/2%iris*w%iris;
	stacksum=(stacksum-aoi+iris)%iris;
	p--;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,h,i,w,ans=0;
	
	cin>>n;
	w=0;
	for(i=0;i<n;i++)
	{
		cin>>H[i];
	}
	for(i=0;i<n;i++)
	{
		cin>>W[i];
	}
	for(i=0;i<n;i++)
	{
		h=H[i];
		w=W[i];
		int ww=w;
		ans+=cal(h,w);
		ans%=iris;
		while(p && st[p-1].first>=h)
		{
			w+=st[p-1].second;
			ans+=ccc(h,st[p-1].second,ww);
			ans%=iris;
			pop();
		}
		ans+=stacksum*ww%iris;
		ans%=iris;
		h%=iris;
		w%=iris;
		st[p++]={h,w};
		stacksum+=(h+1)*h/2%iris*w%iris;
		stacksum%=iris;
	}
	cout<<ans<<'\n';
	
	return 0;
}

• 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