402021-01-08 20:33:44mraronFancy Fencecpp11Elfogadva 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;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva2ms1752 KiB
2Elfogadva2ms1800 KiB
subtask212/12
3Elfogadva1ms1864 KiB
4Elfogadva1ms1864 KiB
5Elfogadva1ms1876 KiB
6Elfogadva1ms1872 KiB
7Elfogadva1ms1880 KiB
subtask313/13
8Elfogadva1ms1948 KiB
9Elfogadva13ms3812 KiB
10Elfogadva24ms6604 KiB
11Elfogadva24ms7776 KiB
12Elfogadva25ms8952 KiB
subtask415/15
13Elfogadva1ms6004 KiB
14Elfogadva4ms6460 KiB
15Elfogadva16ms8492 KiB
16Elfogadva30ms12080 KiB
17Elfogadva30ms14160 KiB
subtask515/15
18Elfogadva2ms11232 KiB
19Elfogadva4ms12364 KiB
20Elfogadva24ms15160 KiB
21Elfogadva34ms21532 KiB
22Elfogadva32ms23404 KiB
subtask618/18
23Elfogadva1ms16164 KiB
24Elfogadva1ms16216 KiB
25Elfogadva2ms16220 KiB
26Elfogadva2ms16264 KiB
27Elfogadva1ms16236 KiB
subtask727/27
28Elfogadva6ms16684 KiB
29Elfogadva8ms16880 KiB
30Elfogadva24ms18792 KiB
31Elfogadva24ms19804 KiB
32Elfogadva28ms23112 KiB
33Elfogadva28ms24868 KiB
34Elfogadva32ms26876 KiB
35Elfogadva28ms28816 KiB
36Elfogadva1ms25888 KiB
37Elfogadva28ms30768 KiB
38Elfogadva28ms32752 KiB
39Elfogadva29ms35576 KiB
40Elfogadva32ms38900 KiB