Submission #1125756

#TimeUsernameProblemLanguageResultExecution timeMemory
1125756dynam1cFancy Fence (CEOI20_fancyfence)C++20
25 / 100
42 ms1864 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;
constexpr ll inv2 = 5e8+4;
ll triples(pair<ll, ll> p) {
  auto [h, w] = p;
  return w * h % mod * (h+1) % mod * inv2 % mod;
}
int main() {
  int n;
  cin >> n;
  vector<ll> h(n), w(n);
  for (auto& e : h)
    cin >> e;
  for (auto& e : w)
    cin >> e;

  ll ans = 0, acc = 0;
  stack<pair<ll, ll>> st; // {h, w}
  auto pop = [&]() {
    acc = (acc + mod - triples(st.top())) % mod;
    st.pop();
  };
  auto push = [&](pair<ll, ll> p) {
    acc = (acc + triples(p)) % mod;
    st.push(p);
  };
  for (int i = 0; i < n; i++) {
    ll popped_width = 0;
    while (!st.empty() && st.top().first >= h[i])
      (popped_width += st.top().second) %= mod, pop();

    push({h[i], popped_width});
    ans = (ans + acc * w[i]) % mod;
    pop();
    push({h[i], (popped_width + w[i]) % mod});
  }

  for (int i = 0; i < n; i++)
    ans = (ans + (h[i]*(h[i]+1) % mod) * (w[i]*(w[i]+1) % mod) * inv2 % mod * inv2 % mod) % mod;

  cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...