402021-01-08 20:33:44mraronFancy Fencecpp11Accepted 100/10034ms38900 KiB
//fancyfence lineáris
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll mod=1e9+7;
const ll inv2=500000004;

#define xx first
#define yy second

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	
	vector<ll> h(n), w(n);
	for(int i=0;i<n;++i) cin>>h[i];
	for(int i=0;i<n;++i) cin>>w[i];
	
	vector<pair<ll,ll>> t; //(height, width)
	t.push_back({0,0});
	
	ll ans=0;
	for(int i=0;i<n;++i) {
		ll wlen=0;
		while(t.back().xx>h[i]) {
			ll prev=max(h[i],t[(int)t.size()-2].xx);
			ll hdiff=t.back().xx-prev;
			wlen=(wlen+t.back().yy)%mod;
			
			t.pop_back();
			
			ans+=(hdiff*(hdiff+1)%mod*inv2%mod+hdiff*prev%mod)*(wlen*(wlen+1)%mod*inv2%mod)%mod;
			ans%=mod;
		}
		
		if(t.back().xx==h[i]) {
			t.back().yy=(t.back().yy+wlen+w[i])%mod;
		}else {
			t.push_back({h[i], (wlen+w[i])%mod});
		}
	}
	
	while((int)t.size()>1) {
		pair<ll,ll> akt=t.back();t.pop_back();
		ll hdiff=akt.xx-t.back().xx;
	
		ans+=(hdiff*(t.back().xx)%mod+hdiff*(hdiff+1)%mod*inv2%mod)*(akt.yy*(akt.yy+1)%mod*inv2%mod)%mod;
		ans%=mod;
		
		t.back().yy+=akt.yy;
		t.back().yy%=mod;
	}
	
	cout<<ans<<"\n";
	return 0;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted2ms1752 KiB
2Accepted2ms1800 KiB
subtask212/12
3Accepted1ms1864 KiB
4Accepted1ms1864 KiB
5Accepted1ms1876 KiB
6Accepted1ms1872 KiB
7Accepted1ms1880 KiB
subtask313/13
8Accepted1ms1948 KiB
9Accepted13ms3812 KiB
10Accepted24ms6604 KiB
11Accepted24ms7776 KiB
12Accepted25ms8952 KiB
subtask415/15
13Accepted1ms6004 KiB
14Accepted4ms6460 KiB
15Accepted16ms8492 KiB
16Accepted30ms12080 KiB
17Accepted30ms14160 KiB
subtask515/15
18Accepted2ms11232 KiB
19Accepted4ms12364 KiB
20Accepted24ms15160 KiB
21Accepted34ms21532 KiB
22Accepted32ms23404 KiB
subtask618/18
23Accepted1ms16164 KiB
24Accepted1ms16216 KiB
25Accepted2ms16220 KiB
26Accepted2ms16264 KiB
27Accepted1ms16236 KiB
subtask727/27
28Accepted6ms16684 KiB
29Accepted8ms16880 KiB
30Accepted24ms18792 KiB
31Accepted24ms19804 KiB
32Accepted28ms23112 KiB
33Accepted28ms24868 KiB
34Accepted32ms26876 KiB
35Accepted28ms28816 KiB
36Accepted1ms25888 KiB
37Accepted28ms30768 KiB
38Accepted28ms32752 KiB
39Accepted29ms35576 KiB
40Accepted32ms38900 KiB