40 2021. 01. 08 20:33:44 mraron Fancy Fence cpp11 Elfogadva 100/100 34ms 38900 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 2ms 1752 KiB
2 Elfogadva 2ms 1800 KiB
subtask2 12/12
3 Elfogadva 1ms 1864 KiB
4 Elfogadva 1ms 1864 KiB
5 Elfogadva 1ms 1876 KiB
6 Elfogadva 1ms 1872 KiB
7 Elfogadva 1ms 1880 KiB
subtask3 13/13
8 Elfogadva 1ms 1948 KiB
9 Elfogadva 13ms 3812 KiB
10 Elfogadva 24ms 6604 KiB
11 Elfogadva 24ms 7776 KiB
12 Elfogadva 25ms 8952 KiB
subtask4 15/15
13 Elfogadva 1ms 6004 KiB
14 Elfogadva 4ms 6460 KiB
15 Elfogadva 16ms 8492 KiB
16 Elfogadva 30ms 12080 KiB
17 Elfogadva 30ms 14160 KiB
subtask5 15/15
18 Elfogadva 2ms 11232 KiB
19 Elfogadva 4ms 12364 KiB
20 Elfogadva 24ms 15160 KiB
21 Elfogadva 34ms 21532 KiB
22 Elfogadva 32ms 23404 KiB
subtask6 18/18
23 Elfogadva 1ms 16164 KiB
24 Elfogadva 1ms 16216 KiB
25 Elfogadva 2ms 16220 KiB
26 Elfogadva 2ms 16264 KiB
27 Elfogadva 1ms 16236 KiB
subtask7 27/27
28 Elfogadva 6ms 16684 KiB
29 Elfogadva 8ms 16880 KiB
30 Elfogadva 24ms 18792 KiB
31 Elfogadva 24ms 19804 KiB
32 Elfogadva 28ms 23112 KiB
33 Elfogadva 28ms 24868 KiB
34 Elfogadva 32ms 26876 KiB
35 Elfogadva 28ms 28816 KiB
36 Elfogadva 1ms 25888 KiB
37 Elfogadva 28ms 30768 KiB
38 Elfogadva 28ms 32752 KiB
39 Elfogadva 29ms 35576 KiB
40 Elfogadva 32ms 38900 KiB