Submission #1216733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216733		MateiKing80	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	69 ms	4252 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int mod = 1e9 + 7, N = 1e5 + 5;

int n, h[N], w[N], sp[N];

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> h[i];
	for (int i = 1; i <= n; i ++) {
		cin >> w[i];
		sp[i] = (sp[i - 1] + w[i]) % mod;
	}
	stack<int> st, st2;
	st.push(0);
	st2.push(0);
	long long sum = 0, rez = 0;
	for (int i = 1; i <= n; i ++) {
		while (h[i] <= h[st.top()]) {
			sum = (sum - st2.top() + mod) % mod;
			st2.pop();
			st.pop();
		}
		sum += (sp[i - 1] - sp[st.top()] + mod) % mod * (h[i] * (h[i] + 1) / 2 % mod) % mod;
		sum %= mod;
		rez += 1LL * sum * w[i] % mod;
		rez %= mod;
		rez += w[i] * (w[i] + 1) / 2 % mod * (h[i] * (h[i] + 1) / 2 % mod) % mod;
		rez %= mod;
		sum += w[i] * (h[i] * (h[i] + 1) / 2 % mod) % mod;
		sum %= mod;
		int c_sum = (sp[i] - sp[st.top()] + mod) % mod * (h[i] * (h[i] + 1) / 2 % mod) % mod;
		st2.push(c_sum);
		st.push(i);
	}
	cout << rez << '\n';
}

• 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