Submission #1364186

#TimeUsernameProblemLanguageResultExecution timeMemory
1364186TraianDanciuFancy Fence (CEOI20_fancyfence)C++20
100 / 100
21 ms3136 KiB
#include <iostream>

using namespace std;

const int MAXN = 100000;
const int MOD = 1000000007;
const int INV2 = (MOD + 1) / 2;

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

int gauss(int n) {
  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++) {
    int sum_left = (spart[i - 1] - spart[l[i]]) % MOD;
    int sum_right = (spart[r[i] - 1] - spart[i]) % MOD;
    int cnt = 0;
    cnt = (cnt + 1LL * sum_left * sum_right) % MOD;
    cnt = (cnt + 1LL * w[i] * (w[i] + 1) / 2) % MOD;
    cnt = (cnt + 1LL * sum_left * w[i]) % MOD;
    cnt = (cnt + 1LL * sum_right * w[i]) % MOD;
    answer = (answer + 1LL * cnt * gauss(h[i])) % MOD;
  }
  cout << answer << "\n";
  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...