Submission #732915

#TimeUsernameProblemLanguageResultExecution timeMemory
732915tvladm2009Fancy Fence (CEOI20_fancyfence)C++17
12 / 100
1 ms340 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
const int N = (int) 1e6 + 7;
const int M = (int) 1e9 + 7;
int h[N], w[N], sp[N], st[N];

int add(int a, int b) {
  a += b;
  a %= M;
  return a;
}

int mul(int a, int b) {
  return (ll) a * b % M;
}

int gauss(int a) {
  return ((ll) a * (a + 1) / 2) % M;
}

int get(int x, int y) {
  return mul(gauss(x), gauss(y));
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    sp[i] = sp[i - 1] + w[i];
  }
  h[n + 1] = 0;
  w[n + 1] = 0;
  sp[n + 1] = sp[n] + w[n + 1];
  n++;
  int vf = 0;
  ll ret = 0;
  for (int i = 1; i <= n; i++) {
    while (vf > 0 && h[i] <= h[st[vf]]) {
      int l = sp[i - 1] - sp[st[vf - 1]];
      ret = add(ret, get(h[st[vf]], l));
      ret = add(ret, -1 * get(max(h[st[vf - 1]], h[i]), l));
      vf--;
    }
    st[++vf] = i;
  }
  ret += M;
  ret %= M;
  cout << ret;
  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...