Submission #1216733

#TimeUsernameProblemLanguageResultExecution timeMemory
1216733MateiKing80Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
69 ms4252 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...