Submission #757808

#	Time	Username	Problem	Language	Result	Execution time	Memory
757808		taher	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	76 ms	6468 KiB

fancyfence

#include <bits/stdc++.h>
 
using namespace std;

constexpr int md = 1000000007;

struct Mint {
  int val = 0;  
  Mint() : val{} {}
  template<typename T> Mint(T x) {
    if (x >= -md && x < md) {
      val = x;
    } else {
      val = x % md;
    }
    if (val < 0) {
      val += md;
    }
  }
  int& operator()() { return val; }
  Mint& operator+=(Mint x) {
    if ((val += x.val) >= md) {
      val -= md;
    }
    return *this;
  }
  Mint& operator-=(Mint x) {
    if ((val -= x.val) < 0) {
      val += md;
    }
    return *this;
  }
  Mint& operator*=(Mint x) {
    val = int((1LL * val * x.val) % md);      
    return *this;
  }
};
template<typename T> Mint power(Mint x, T p) {
  Mint res = 1;
  while (p > 0) {
    if (p & 1) {
      res *= x;
    }
    x *= x;
    p >>= 1;
  }
  return res;
}
Mint& operator/=(Mint& x, Mint y) {
  return x *= power(y, md - 2);
}
 
Mint operator+(Mint x, Mint y) {
  return x += y;
}
Mint operator-(Mint x, Mint y) {
  return x -= y;
}
Mint operator*(Mint x, Mint y) {
  return x *= y;
}
Mint operator/(Mint x, Mint y) {
  return x /= y;
}
string to_string(Mint x) {
  return to_string(x());
}
ostream& operator<<(ostream& out, Mint x) {
  return out << x();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i].second;
  }
  // {n, m}
  vector<long long> pref(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) pref[i] = pref[i - 1];
    pref[i] += a[i].second;
  }
  vector<long long> ans(n), rmv(n);
  auto Left = [&]() {
    vector<pair<int, int>> stk;
    for (int i = 0; i < n; i++) {
      while (!stk.empty() && stk.back().first > a[i].first) {
        stk.pop_back();
      }
      int new_idx = (stk.empty() ? -1 : stk.back().second);
      while (!stk.empty() && stk.back().first == a[i].first) {
        stk.pop_back();
      }
      int idx = (stk.empty() ? -1 : stk.back().second);
      stk.emplace_back(a[i].first, i);
      ans[i] += pref[i] - (idx >= 0 ? pref[idx] : 0);
      rmv[i] = max(rmv[i], (new_idx >= 0 ? a[new_idx].first : 0LL));
    }
  };
  auto Right = [&]() {
    vector<pair<int, int>> stk;
    for (int i = n - 1; i >= 0; i--) {
      while (!stk.empty() && stk.back().first >= a[i].first) {
        stk.pop_back();
      }
      int idx = (stk.empty() ? n : stk.back().second);
      stk.emplace_back(a[i].first, i);
      ans[i] += pref[idx - 1] - pref[i];
      rmv[i] = max(rmv[i], (idx < n ? a[idx].first : 0LL));
    }
  };
  Left();
  Right();
  Mint res = 0;
  for (int i = 0; i < n; i++) {
    Mint N = a[i].first;
    Mint M = ans[i];
    res += (N * (N + 1)) / 2 * (M * (M + 1)) / 2;
    res -= (rmv[i] * (rmv[i] + 1)) / 2 * (M * (M + 1)) / 2;
  }
  cout << res << '\n';
  return 0; 
}

• 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