Submission #1125754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125754		dynam1c	Fancy Fence (CEOI20_fancyfence)	C++20	25 / 100	41 ms	1864 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9+7;
constexpr int 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]});
  }

  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;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27