제출 #1280333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280333		behrad	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	20 ms	3188 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e5+5, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, w[maxn], h[maxn], l[maxn], r[maxn];
ll ps[maxn], ans;

inline ll C2(ll x) {
  return (x * (x - 1) / 2) % mod;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n;
  for (int i = 1 ; i <= n ; i ++) cin >> h[i];
  for (int i = 1 ; i <= n ; i ++) cin >> w[i];
  for (int i = 1 ; i <= n ; i ++) ps[i] = ps[i - 1] + w[i];
  vector<int> stk;
  for (int i = 1 ; i <= n ; i ++) {
    while (stk.size() && h[stk.back()] > h[i]) stk.pop_back();
    l[i] = stk.size() ? stk.back() : 0;
    stk.pb(i);
  }
  stk.clear();
  for (int i = n ; i >= 1 ; i --) {
    while (stk.size() && h[stk.back()] >= h[i]) stk.pop_back();
    r[i] = stk.size() ? stk.back() : n+1;
    stk.pb(i);
  }

  ll ans = 0;
  for (int i = 1 ; i <= n ; i ++) {
    ll lf = (ps[i - 1] - ps[l[i]] + mod) % mod, rt = (ps[r[i] - 1] - ps[i] + mod) % mod;

    ll H = C2(h[i] + 1);
    ll W = lf * (w[i] + rt) % mod + w[i] * rt % mod + C2(w[i] + 1);
    while (W >= mod) W -= mod;
    ans = (ans + H * W) % mod;
  }
  cout << ans << nl;
}

• 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