1382021-01-29 20:05:36mraronFancy Fencecpp11Elfogadva 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;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms1752 KiB
2Elfogadva1ms1824 KiB
subtask212/12
3Elfogadva1ms1860 KiB
4Elfogadva1ms1868 KiB
5Elfogadva1ms1900 KiB
6Elfogadva1ms1888 KiB
7Elfogadva1ms1900 KiB
subtask313/13
8Elfogadva2ms1932 KiB
9Elfogadva18ms3820 KiB
10Elfogadva34ms6620 KiB
11Elfogadva35ms7784 KiB
12Elfogadva28ms8944 KiB
subtask415/15
13Elfogadva1ms6004 KiB
14Elfogadva4ms6424 KiB
15Elfogadva14ms8496 KiB
16Elfogadva28ms12076 KiB
17Elfogadva27ms14160 KiB
subtask515/15
18Elfogadva2ms11232 KiB
19Elfogadva4ms12280 KiB
20Elfogadva16ms15160 KiB
21Elfogadva30ms21484 KiB
22Elfogadva29ms23428 KiB
subtask618/18
23Elfogadva1ms16164 KiB
24Elfogadva1ms16180 KiB
25Elfogadva1ms16200 KiB
26Elfogadva1ms16212 KiB
27Elfogadva1ms16232 KiB
subtask727/27
28Elfogadva4ms16656 KiB
29Elfogadva4ms16848 KiB
30Elfogadva14ms18888 KiB
31Elfogadva16ms19808 KiB
32Elfogadva29ms23112 KiB
33Elfogadva29ms24872 KiB
34Elfogadva29ms26872 KiB
35Elfogadva28ms28820 KiB
36Elfogadva1ms25864 KiB
37Elfogadva32ms30772 KiB
38Elfogadva32ms32720 KiB
39Elfogadva29ms35588 KiB
40Elfogadva28ms38864 KiB