Submission #1289472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289472		LIA	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	1 ms	576 KiB

fancyfence

//
// Created by liasa on 11/11/2025.
//

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
const ll mod = 1e9 + 7;

ll pw(ll a, ll b) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
      b--;
    }
    b /= 2;
    a = (a * a) % mod;
  }
  return ans;
}

ll invi(ll x) { return pw(x, mod - 2); }

ll mul(ll a, ll b) { return (ll)((__int128)a * b % mod); }

ll addi(ll H, ll W) {
  H++;
  W++;
  ll a = mul(H % mod, (H - 1) % mod);
  ll b = mul(W % mod, (W - 1) % mod);
  ll inv2 = invi(2);
  ll ans = mul(mul(a, b), mul(inv2, inv2));
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin >> n;
  vll h(n), w(n);
  vll pre(n + 2);
  for (ll i = 0; i < n; ++i) {
    cin >> h[i];
  }
  for (ll i = 0; i < n; ++i) {
    cin >> w[i];
    pre[i + 1] = pre[i] + w[i];
  }
  vll left(n);
  stack<ll> s;
  for (ll i = 0; i < n; ++i) {
    while (!s.empty() && h[s.top()] >= h[i])
      s.pop();
    left[i] = s.empty() ? 0 : s.top() + 1;
    s.push(i);
  }
  while (!s.empty())
    s.pop();

  vll right(n);

  for (ll i = n - 1; i >= 0; --i) {
    while (!s.empty() && h[s.top()] > h[i])
      s.pop();
    right[i] = s.empty() ? n : s.top() + 1;
    s.push(i);
  }

  ll ans = 0;

  auto sumi = [&pre](ll l, ll r) -> ll {
    return (l > r) ? 0 : pre[r + 1] - pre[l];
  };
  for (ll i = 0; i < n; ++i) {
    ll L = sumi(left[i], i - 1);
    ll C = w[i];
    ll R = sumi(i + 1, right[i] - 1);
    ll T = (L + C + R) % mod;
    ll vert = addi(1, h[i]);
    ll hori = (addi(1, T) - addi(1, L) - addi(1, R)) % mod;
    if (hori < 0)
      hori += mod;
    ans = (ans + mul(vert, hori)) % mod;
  }

  cout << ans;
}

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