Submission #1086471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086471		juicy	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	26 ms	3552 KiB

fancyfence

#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;
}

• 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