fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define Chris ""
  4. #define Fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
  5. #define File(Chris) if(std::fopen(Chris".inp", "r")){std::freopen(Chris".inp", "r", stdin);std::freopen(Chris".out", "w", stdout);}
  6.  
  7. template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y){x = y; return true;} else return false;}
  8. template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y){x = y; return true;} else return false;}
  9.  
  10. static constexpr long long mod = 1e9 + 7;
  11. static constexpr long long INF = (long long) 1e18;
  12. static constexpr int MAXN = (int) 1e5 + 5;
  13.  
  14. void add(int &x, int y) {
  15. x += y;
  16. if (x >= mod) x -= mod;
  17. }
  18.  
  19. #define int long long
  20.  
  21. int n;
  22.  
  23. long long calc(int x){
  24. x %= mod;
  25. long long ans = (x * (x + 1)) >> 1;
  26. ans %= mod;
  27. return ans;
  28. }
  29.  
  30. void Inp(){
  31. std::cin >> n;
  32. }
  33.  
  34. void Solve() {
  35. Inp();
  36. std::vector<long long> h(n + 1);
  37. std::vector<long long> w(n + 1);
  38. std::vector<long long> prefixW(n + 1, 0);
  39. for (int i = 1; i <= n; ++i) std::cin >> h[i];
  40. for (int i = 1; i <= n; ++i) {
  41. std::cin >> w[i];
  42. prefixW[i] = prefixW[i - 1] + w[i];
  43. }
  44. std::vector<int> L(n + 1, 0);
  45. std::vector<int> R(n + 1, n + 1);
  46. std::stack<int> st;
  47. for (int i = 1; i <= n; ++i) {
  48. while (!st.empty() && h[st.top()] >= h[i]) {
  49. st.pop();
  50. }
  51. if (!st.empty()) L[i] = st.top();
  52. st.push(i);
  53. }
  54. while (!st.empty()) st.pop();
  55. for (int i = n; i >= 1; --i) {
  56. while (!st.empty() && h[st.top()] > h[i]) {
  57. st.pop();
  58. }
  59. if (!st.empty()) R[i] = st.top();
  60. st.push(i);
  61. }
  62. long long ans = 0;
  63. for(int i = 1; i <= n; ++i){
  64. int l = L[i] + 1;
  65. int r = R[i] - 1;
  66. long long vatngangquaI = (calc(prefixW[r] - prefixW[l - 1]) - calc(prefixW[i - 1] - prefixW[l - 1]) - calc(prefixW[r] - prefixW[i])) % mod;
  67. if(vatngangquaI < 0) vatngangquaI += mod;
  68. long long contribution = (vatngangquaI * calc(h[i])) % mod;
  69. ans = (ans + contribution) % mod;
  70. }
  71. std::cout << ans << '\n';
  72. return;
  73. }
  74.  
  75. signed main() {
  76. Fast
  77. File(Chris)
  78.  
  79. Solve();
  80.  
  81. return 0;
  82. }
Success #stdin #stdout 0.01s 5324KB
stdin
Standard input is empty
stdout
0