Submission #915439

#	Time	Username	Problem	Language	Result	Execution time	Memory
915439		null_awe	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	2 ms	464 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>

const int MOD = 1e9 + 7;
const int INV2 = 500000004;

int32_t main() {
  int n; cin >> n;
  vector<int> h(n), w(n);
  for (int i = 0; i < n; ++i) cin >> h[i];
  for (int i = 0; i < n; ++i) cin >> w[i];
  stack<int> hsum, area;
  stack<pii> hs;
  hsum.push(0), area.push(0);
  hs.push({0, 0});
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    // add indiv to answer:
    ans += (h[i] * (h[i] + 1) / 2 % MOD) * (w[i] * (w[i] + 1) / 2 % MOD) % MOD;
    // remove unneccesary:
    int nw = 0;
    while (hs.top().first > h[i]) nw += hs.top().second, hsum.pop(), area.pop(), hs.pop();
    // insert (h[i], nw):
    int lh = hs.top().first + 1;
    hsum.push((hsum.top() + (h[i] + lh) % MOD * (h[i] - lh + 1) % MOD * INV2 % MOD) % MOD);
    area.push((area.top() + hsum.top() * nw % MOD) % MOD);
    // add rest to answer:
    ans = (ans + area.top()) % MOD;
    // insert (h[i], w[i]):
    lh = hs.top().first + 1;
    hsum.push((hsum.top() + (h[i] + lh) % MOD * (h[i] - lh + 1) % MOD * INV2 % MOD) % MOD);
    area.push((area.top() + hsum.top() * w[i] % MOD) % MOD);
  }
  cout << ans << '\n';
  return 0;
}


/*
System.out.println("Hello World");
public static double yamom(String "s"){

}
*/

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27