Submission #732921

#	Time	Username	Problem	Language	Result	Execution time	Memory
732921		tvladm2009	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	34 ms	5360 KiB

fancyfence

#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) {
  x %= M;
  y %= M;
  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;
}

• 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