제출 #1289479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289479		LIA	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	41 ms	4024 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;
}

ll CH(ll H) {
  H++;
  ll inv2 = invi(2);
  return mul(mul(H % mod, (H - 1) % mod), inv2);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin >> n;
  vll h(n), w(n);
  for (ll i = 0; i < n; i++)
    cin >> h[i];
  vll pre(n + 1, 0);
  for (ll i = 0; i < n; i++) {
    cin >> w[i];
    pre[i + 1] = pre[i] + w[i];
  }

  ll ans = 0;
  for (ll i = 0; i < n; i++) {
    ans += addi(h[i], w[i]);
    ans = (ans + mod) % mod;
  }

  vector<ll> s;
  for (ll i = 0; i <= n; i++) {
    ll cur = (i < n ? h[i] : -1);
    while (!s.empty() && h[s.back()] >= cur) {
      ll j = s.back();
      s.pop_back();
      ll L = s.empty() ? 0 : s.back() + 1, R = i - 1;
      ll sum_l = pre[j + 1] - pre[L];
      ll sum_r = pre[R + 1] - pre[j];
      ll fixi = CH(h[j]);
      ll ad = mul(
          ((mul(sum_l % mod, sum_r % mod) - mul(w[j] % mod, w[j] % mod) + mod) %
           mod),
          fixi);
      ans += ad;
      ans = (ans + mod) % mod;
    }
    if (i < n)
      s.push_back(i);
  }

  cout << ans;
}

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