Submission #915450

#	Time	Username	Problem	Language	Result	Execution time	Memory
915450		null_awe	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	76 ms	5460 KiB

fancyfence

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

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

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

// ifstream cin("a");
// ofstream cout("b");

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;
    // cout << ans << ' ';
    // remove unneccesary:
    int nw = 0;
    while (hs.top().first >= h[i]) nw = (nw + hs.top().second) % MOD, hsum.pop(), area.pop(), hs.pop();
    // insert (h[i], nw):
    // cout << "nw " << nw << ' ';
    int lh = hs.top().first + 1;
    if (nw > 0) {
      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);
      hs.push({h[i], w[i]});
    }
    // add rest to answer:
    ans = (ans + w[i] * area.top() % MOD) % MOD;
    // insert (h[i], w[i]):
    if (nw > 0) hsum.pop(), area.pop(), hs.pop();
    lh = hs.top().first + 1;
    w[i] = (w[i] + nw) % MOD;
    // cout << lh << ' ' << h[i] << ' ';
    hsum.push((hsum.top() + (h[i] + lh) % MOD * (h[i] - lh + 1) % MOD * INV2 % MOD) % MOD);
    // cout << hsum.top() << ' ';
    area.push((area.top() + hsum.top() * w[i] % MOD) % MOD);
    hs.push({h[i], w[i]});
    // cout << ans << '\n';
  }
  cout << ans << '\n';
  return 0;
}


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

}
*/

• 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