fork download
  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
stdin
2
1 2
1 2
stdout
12