138 2021. 01. 29 20:05:36 mraron Fancy Fence cpp11 Elfogadva 100/100 35ms 38864 KiB
#include<bits/stdc++.h>
using namespace std;

#define xx first
#define yy second

//
// O(N) solution to fancyfance by Áron Noszály
// 
// Maintains a stack of sections with increasing height.
// At every iteration we insert the current section and merge it with some at the top of the stack with greater height,
// they will become one "new" section with height of the current while we just count those fancyrectangles that will no longer be present in the stack.
// There are some not so hard formulas to find the number of these.
// We can add a dummy 0*0 section after the input sections to make the implementation easier.
//

using ll=long long;
const ll mod=1e9+7;
const ll inv2=500000004; //2^-1 mod 10^9+7

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	vector<ll> h(n+1,0), w(n+1,0);
	for(int i=0;i<n;++i) cin>>h[i];
	for(int i=0;i<n;++i) cin>>w[i];
	n++; // Adding the dummy one.
	
	vector<pair<ll,ll>> t; // The stack, with (height, width) pairs,
	t.push_back({0,0});
	
	ll ans=0;
	for(int i=0;i<n;++i) {
		ll w_len=0; // this the sum of widths of sections removed from to have the current one inserted,
		while(t.back().xx>h[i]) { // we can't insert (h[i];w[i]) currently while maintaining sortedness,
			// the previous height, we need to only consider at least heights of h[i] since those fancyrectangles that lie at smaller heights will be considered later,
			ll h_prev=max(h[i],t[(int)t.size()-2].xx); 
			ll h_diff=t.back().xx-h_prev; // difference between the heights,
			w_len=(w_len+t.back().yy)%mod; // maintain w_len.
			
			t.pop_back();
			
			// Now comes the formula, notice that our problem basically boils down to having a h_prev*w_len rectangle and we 
			// want to count the number of rectangles having a non-empty (with area) intersection with the top h_diff*w_len part of this rectangle.
			// We can notice that we independently can choose an interval on the "side" of the big rectangle which represents the small one's height and width.
			
			// For the height part:
			// * consider only those that are above h_prev, there are (h_diff+1 choose 2)=(h_diff choose 2)+h_diff ways to place
			// * consider those rectangles that have their top in the top part but their bottom part goes down, there are h_diff*h_prev ways to choose
			
			// For the width part:
			// * there are w_len+(w_len choose 2)=(w_len+1 choose 2) ways
			ans+=(h_diff*(h_diff+1)%mod*inv2%mod+h_diff*h_prev%mod)*(w_len*(w_len+1)%mod*inv2%mod)%mod;
			ans%=mod;
		}
		
		// If the top one has h[i] height just add the width to it, else push a new section into the stack.
		if(t.back().xx==h[i]) {
			t.back().yy=(t.back().yy+w_len+w[i])%mod;
		}else {
			t.push_back({h[i], (w_len+w[i])%mod});
		}
	}
	
	cout<<ans<<"\n";
	return 0;
}

Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 1ms 1752 KiB
2 Elfogadva 1ms 1824 KiB
subtask2 12/12
3 Elfogadva 1ms 1860 KiB
4 Elfogadva 1ms 1868 KiB
5 Elfogadva 1ms 1900 KiB
6 Elfogadva 1ms 1888 KiB
7 Elfogadva 1ms 1900 KiB
subtask3 13/13
8 Elfogadva 2ms 1932 KiB
9 Elfogadva 18ms 3820 KiB
10 Elfogadva 34ms 6620 KiB
11 Elfogadva 35ms 7784 KiB
12 Elfogadva 28ms 8944 KiB
subtask4 15/15
13 Elfogadva 1ms 6004 KiB
14 Elfogadva 4ms 6424 KiB
15 Elfogadva 14ms 8496 KiB
16 Elfogadva 28ms 12076 KiB
17 Elfogadva 27ms 14160 KiB
subtask5 15/15
18 Elfogadva 2ms 11232 KiB
19 Elfogadva 4ms 12280 KiB
20 Elfogadva 16ms 15160 KiB
21 Elfogadva 30ms 21484 KiB
22 Elfogadva 29ms 23428 KiB
subtask6 18/18
23 Elfogadva 1ms 16164 KiB
24 Elfogadva 1ms 16180 KiB
25 Elfogadva 1ms 16200 KiB
26 Elfogadva 1ms 16212 KiB
27 Elfogadva 1ms 16232 KiB
subtask7 27/27
28 Elfogadva 4ms 16656 KiB
29 Elfogadva 4ms 16848 KiB
30 Elfogadva 14ms 18888 KiB
31 Elfogadva 16ms 19808 KiB
32 Elfogadva 29ms 23112 KiB
33 Elfogadva 29ms 24872 KiB
34 Elfogadva 29ms 26872 KiB
35 Elfogadva 28ms 28820 KiB
36 Elfogadva 1ms 25864 KiB
37 Elfogadva 32ms 30772 KiB
38 Elfogadva 32ms 32720 KiB
39 Elfogadva 29ms 35588 KiB
40 Elfogadva 28ms 38864 KiB