fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define f first
  5. #define s second
  6. #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7.  
  8. ll mod=1000000007;
  9. ll h[200005],w[200005],pre[200005];
  10.  
  11. ll C(ll x,ll y){
  12. 	ll ans=(x*(x+1)/2)%mod;
  13. 	ll ans1=(y*(y+1)/2)%mod;
  14. 	ll a=(ans*ans1)%mod;
  15. 	return a;
  16. }
  17.  
  18. int main() {_
  19. 	ll n;
  20. 	cin>>n;
  21. 	for(ll i=1;i<=n;i++){
  22. 		cin>>h[i];
  23. 	}
  24. 	h[0]=0;
  25. 	pre[0]=0;
  26. 	w[0]=0;
  27. 	for(ll i=1;i<=n;i++){
  28. 		cin>>w[i];
  29. 		pre[i]=(pre[i-1]+w[i])%mod;
  30. 	}
  31. 	stack<ll> s;
  32. 	s.push(0);
  33. 	ll ans=0;
  34. 	for(ll i=1;i<=n;i++){
  35. 		while(s.size()>1 and h[s.top()]>h[i]){
  36. 			ll x=s.top();
  37. 			s.pop();
  38. 			ll y=s.top();
  39. 			ans+=(C(h[x],pre[i-1]-pre[y])-C(h[y],pre[i-1]-pre[y]))%mod;
  40. 			ans%=mod;
  41. 		}
  42. 		s.push(i);
  43. 	}
  44. 	while(s.size()>1){
  45. 		ll x=s.top();
  46. 		s.pop();
  47. 		ll y=s.top();
  48. 		ans+=(C(h[x],pre[n]-pre[y])-C(h[y],pre[n]-pre[y]))%mod;
  49. 		ans%=mod;
  50. 	}
  51. 	ans%=mod;
  52. 	cout<<ans;
  53. 	return 0;
  54. }
  55. //maybe its multiset not set
Success #stdin #stdout 0.01s 5632KB
comments (?)
stdin
copy 
2
1 2
1 2
stdout
copy 
12
https://ideone.com/pagI2z
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!