Submission #1086471

#TimeUsernameProblemLanguageResultExecution timeMemory
1086471juicyFancy Fence (CEOI20_fancyfence)C++17
100 / 100
26 ms3552 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int M = 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= M) {
    x -= M;
  }
  if (x < 0) {
    x += M;
  } 
}

int C2(int x) {
  return (long long) x * (x + 1) / 2 % M;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n; cin >> n;
  vector<int> h(n), w(n);
  for (int &x : h) {
    cin >> x;
  }
  vector<int> st;
  int sum = 0, res = 0;
  for (int i = 0; i < n; ++i) {
    cin >> w[i];
    int x = 0;
    while (st.size() && h[st.back()] >= h[i]) {
      add(x, w[st.back()]);
      add(sum, (long long) -w[st.back()] * C2(h[st.back()]) % M);
      st.pop_back();
    }
    add(res, (long long) w[i] * x % M * C2(h[i]) % M);
    add(res, (long long) w[i] * sum % M);
    add(res, (long long) C2(w[i]) * C2(h[i]) % M);
    add(x, w[i]);
    w[i] = x;
    add(sum, (long long) w[i] * C2(h[i]) % M);
    st.push_back(i);
  } 
  cout << res; 
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...