제출 #468382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468382		thomas_li	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	107 ms	4952 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
template <class T, class U> T pow2(T base, U pow) {
  T x = 1; while (true) {
    if (pow % 2 == 1) x = x * base;
    if ((pow /= 2) == 0) break;
    base = base * base;
  }
  return x;
}
template <class T> constexpr bool isPrime(T x) {
  if (x < 2) return false;
  for (T i = 2; i * i <= x; i++) if (x % i == 0) return false;
  return true;
}
template <class T, const T MOD,
#if __cplusplus < 201402L
          const bool PRIME_MOD,
#else
          const bool PRIME_MOD = isPrime(MOD),
#endif
          const bool MUL_OVERFLOW = (numeric_limits<T>::max() / MOD < MOD)>
    struct IntMod {
  static_assert(is_integral<T>::value, "T must be an integral type");
  static_assert(is_signed<T>::value, "T must be a signed type");
  static_assert(0 < MOD, "MOD must be a positive integer");
  using IM = IntMod<T, MOD, PRIME_MOD, MUL_OVERFLOW>;
  T v; IntMod() : v(0) {}
  IntMod(const T &x) {
    v = -MOD < x && x < MOD ? x : x % MOD; if (v < 0) v += MOD;
  }
  bool operator < (const IM &i) const { return v < i.v; }
  bool operator <= (const IM &i) const { return v <= i.v; }
  bool operator > (const IM &i) const { return v > i.v; }
  bool operator >= (const IM &i) const { return v >= i.v; }
  bool operator == (const IM &i) const { return v == i.v; }
  bool operator != (const IM &i) const { return v != i.v; }
  IM operator ++ () {
    if (++v == MOD) v = 0;
    return *this;
  }
  IM operator ++ (int) {
    IM ret = *this; if (++v == MOD) v = 0;
    return ret;
  }
  IM operator -- () {
    if (v-- == 0) v = MOD - 1;
    return *this;
  }
  IM operator -- (int) {
    IM ret = *this; if (v-- == 0) v = MOD - 1; return ret;
  }
  IM operator + (const IM &i) const { return IM(*this) += i; }
  IM &operator += (const IM &i) {
    if ((v += i.v) >= MOD) v -= MOD;
    return *this;
  }
  IM operator - (const IM &i) const { return IM(*this) -= i; }
  IM &operator -= (const IM &i) {
    if ((v -= i.v) < 0) v += MOD;
    return *this;
  }
  IM operator + () const { return *this; }
  IM operator - () const { return IM(-v); }
  IM operator * (const IM &i) const { return IM(*this) *= i; }
  IM &operator *= (const IM &i) {
    if (MUL_OVERFLOW) {
      IM x = 0, y = *this; T z = i.v;
      for (; z > 0; z /= 2, y += y) if (z % 2 == 1) x += y;
      *this = x;
    } else v = v * i.v % MOD;
    return *this;
  }
  bool hasMulInv() const {
    if (v == 0) return false;
    if (!PRIME_MOD || MUL_OVERFLOW) {
      T g = MOD, r = v; while (r != 0) { g %= r; swap(g, r); }
      return g == 1;
    } else return true;
  }
  IM mulInv() const {
    if (!PRIME_MOD || MUL_OVERFLOW) {
      T g = MOD, r = v, x = 0, y = 1; while (r != 0) {
        T q = g / r; g %= r; swap(g, r); x -= q * y; swap(x, y);
      }
      assert(g == 1); return IM(x);
    } else return pow2(*this, MOD - 2);
  }
  IM operator / (const IM &i) const { return IM(*this) /= i; }
  IM &operator /= (const IM &i) { return *this *= i.mulInv(); }
  friend istream &operator >> (istream &stream, IM &i) {
    T v; stream >> v; i = IM(v); return stream;
  }
  friend ostream &operator << (ostream &stream, const IM &i) {
    return stream << i.v;
  }
};
const int MM = 1e5+5,MOD = 1e9+7,inv2 = 500000004;
typedef IntMod<ll,MOD> IM;

int n,h[MM],w[MM]; IM psa[MM],dp[MM];
IM c2(int x){
    IM res(x);
    return res*(res+1)/2;
}
signed 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],psa[i] = psa[i-1] + w[i];
    stack<int> st; st.push(0);
    IM ans(0);
    for(int i = 1; i <= n; i++){
        while(st.size() && h[st.top()] >= h[i]) st.pop(); 
        int j = st.top();
        dp[i] = dp[j];     
        dp[i] += (psa[i] - psa[j])*c2(h[i]);
        ans += dp[j]*w[i] + c2(w[i])*c2(h[i]);
        ans += (psa[i-1] - psa[j])*w[i]*c2(h[i]);
        st.push(i);
    }
    cout << ans << "\n";
}

• 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