Submission #1202678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202678		pera	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	17 ms	2644 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
template <long long MOD = 1000000007, typename T = int> struct modint {
   T x;
   modint() : x(0) {}
   modint(int64_t y) : x(y >= 0 ? y % MOD : (MOD - (-y) % MOD) % MOD) {}
   modint &operator+=(const modint &p) {
      if ((x += p.x) >= MOD) x -= MOD;
      return *this;
   }
   modint &operator-=(const modint &p) {
      if ((x += MOD - p.x) >= MOD) x -= MOD;
      return *this;
   }
   modint &operator*=(const modint &p) {
      x = (int)(1LL * x * p.x % MOD);
      return *this;
   }
   modint &operator/=(const modint &p) {
      *this *= p.inv();
      return *this;
   }
   modint operator-() const { return modint(-x); }
   modint operator+(const modint &p) const { return modint(*this) += p; }
   modint operator-(const modint &p) const { return modint(*this) -= p; }
   modint operator*(const modint &p) const { return modint(*this) *= p; }
   modint operator/(const modint &p) const { return modint(*this) /= p; }
   bool operator==(const modint &p) const { return x == p.x; }
   bool operator!=(const modint &p) const { return x != p.x; }
   modint inv() const {
      T a = x, b = MOD, u = 1, v = 0, t;
      while (b > 0) {
         t = a / b;
         swap(a -= t * b, b);
         swap(u -= t * v, v);
      }
      return modint(u);
   }
   modint pow(int64_t n) const {
      modint ret(1), mul(x);
      while (n > 0) {
         if (n & 1) ret *= mul;
         mul *= mul;
         n >>= 1;
      }
      return ret;
   }
   friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; }
   friend istream &operator>>(istream &is, modint &a) {
      int64_t t;
      is >> t;
      a = modint<MOD>(t);
      return (is);
   }
   T val() const { return x; }
   static constexpr T mod() { return MOD; }
   static constexpr T half() { return (MOD + 1) >> 1; }
};
//--
using Mint = modint<1000000007>;
int main(){
   cin.tie(0)->sync_with_stdio(0);
   int n;
   cin >> n;
   vector<long long> h(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> h[i];
   }
   vector<Mint> w(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> w[i];
   }
   vector<int> L(n + 1);
   for(int i = 1;i <= n;i ++){
      L[i] = i - 1;
      while(L[i] > 0 && h[i] < h[L[i]]){
         L[i] = L[L[i]];
      }
   }
   vector<int> R(n + 1);
   for(int i = n;i >= 1;i --){
      R[i] = i + 1;
      while(R[i] <= n && h[i] <= h[R[i]]){
         R[i] = R[R[i]];
      }
   }
   Mint ans = 0;
   vector<Mint> sum(n + 1);
   for(int i = 1;i <= n;i ++){
      sum[i] = sum[i - 1] + w[i];
   }
   for(int i = 1;i <= n;i ++){
      ans += w[i] * (w[i] + 1) * Mint(h[i]) * Mint(h[i] + 1) / 4; 
      ans += ((sum[i] - sum[L[i]]) * (sum[R[i] - 1] - sum[i - 1]) - w[i] * w[i]) * Mint(h[i]) * Mint(h[i] + 1) / 2;
   }
   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