1382021-01-29 20:05:36mraronFancy Fencecpp11Accepted 100/10035ms38864 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;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1752 KiB
2Accepted1ms1824 KiB
subtask212/12
3Accepted1ms1860 KiB
4Accepted1ms1868 KiB
5Accepted1ms1900 KiB
6Accepted1ms1888 KiB
7Accepted1ms1900 KiB
subtask313/13
8Accepted2ms1932 KiB
9Accepted18ms3820 KiB
10Accepted34ms6620 KiB
11Accepted35ms7784 KiB
12Accepted28ms8944 KiB
subtask415/15
13Accepted1ms6004 KiB
14Accepted4ms6424 KiB
15Accepted14ms8496 KiB
16Accepted28ms12076 KiB
17Accepted27ms14160 KiB
subtask515/15
18Accepted2ms11232 KiB
19Accepted4ms12280 KiB
20Accepted16ms15160 KiB
21Accepted30ms21484 KiB
22Accepted29ms23428 KiB
subtask618/18
23Accepted1ms16164 KiB
24Accepted1ms16180 KiB
25Accepted1ms16200 KiB
26Accepted1ms16212 KiB
27Accepted1ms16232 KiB
subtask727/27
28Accepted4ms16656 KiB
29Accepted4ms16848 KiB
30Accepted14ms18888 KiB
31Accepted16ms19808 KiB
32Accepted29ms23112 KiB
33Accepted29ms24872 KiB
34Accepted29ms26872 KiB
35Accepted28ms28820 KiB
36Accepted1ms25864 KiB
37Accepted32ms30772 KiB
38Accepted32ms32720 KiB
39Accepted29ms35588 KiB
40Accepted28ms38864 KiB