제출 #1364176

#제출 시각아이디문제언어결과실행 시간메모리
1364176TraianDanciuFancy Fence (CEOI20_fancyfence)C++20
0 / 100
0 ms348 KiB
#include <iostream>

using namespace std;

const int MAXN = 100000;
const int MOD = 1000000007;

int h[MAXN + 2], w[MAXN + 2], l[MAXN + 1], r[MAXN + 1], stiva[MAXN + 1];
long long spart[MAXN + 1];

int gauss(long long n) {
  n %= MOD;
  return 1LL * n * (n + 1) / 2 % MOD;
}

void addSelf(int &a, int b) {
  a += b;
  if(a >= MOD) {
    a -= MOD;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.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];
    spart[i] = spart[i - 1] + w[i];
  }

  int sp = 1;
  h[0] = 0;
  stiva[0] = 0;
  for(int i = 1; i <= n; i++) {
    while(sp > 0 && h[stiva[sp - 1]] >= h[i]) {
      sp--;
    }
    l[i] = stiva[sp - 1];
    stiva[sp++] = i;
  }

  sp = 1;
  h[n + 1] = 0;
  stiva[0] = n + 1;
  for(int i = n; i >= 1; i--) {
    while(sp > 0 && h[stiva[sp - 1]] > h[i]) {
      sp--;
    }
    r[i] = stiva[sp - 1];
    stiva[sp++] = i;
  }

  int answer = 0;
  for(int i = 1; i <= n; i++) {
    long long sum_left = spart[i - 1] - spart[l[i]];
    long long sum_right = spart[r[i] - 1] - spart[i];
    int cnt = 0;
    cnt = (cnt + 1LL * sum_left * sum_right % MOD * w[i]) % MOD;
    cnt = (cnt + 1LL * gauss(sum_left) * sum_right) % MOD;
    cnt = (cnt + 1LL * sum_left * gauss(sum_right)) % MOD;
    addSelf(cnt, gauss(w[i]));
    cnt = (cnt + 1LL * sum_left * gauss(w[i])) % MOD;
    cnt = (cnt + 1LL * gauss(sum_left) * w[i]) % MOD;
    cnt = (cnt + 1LL * gauss(w[i]) * sum_right) % MOD;
    cnt = (cnt + 1LL * w[i] * gauss(sum_right)) % MOD;
    answer = (answer + 1LL * cnt * h[i]) % MOD;
  }
  cout << answer << "\n";
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…