제출 #674790

#제출 시각아이디문제언어결과실행 시간메모리
674790IliyaFancy Fence (CEOI20_fancyfence)C++17
100 / 100
32 ms5068 KiB
#include<bits/stdc++.h>
#define pb push_back

using namespace std;
typedef long long ll;
const int N = 1e5 + 10, MOD = 1e9 + 7;

int power(int a, int b) {
	if(b == 0)
		return 1;
	int res = power(a, b / 2);
	res = 1LL * res * res % MOD;
	if(b & 1) res = 1LL * res * a % MOD;
	return res;
}

int two = power(2, MOD - 2);
int C2(int a) { return 1LL * a * (a - 1) % MOD * two % MOD; }

int H[N], W[N], L[N], PS[N], M[N], len[N], n;
ll ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> H[i];
	for(int i = 1; i <= n; i++) 
		cin >> W[i], PS[i] = (W[i] + PS[i - 1]) % MOD;
	stack<int> st;
	for(int i = 1; i <= n; i++) {
		while(!st.empty() and H[i] <= H[st.top()]) st.pop();
		L[i] = ((int) st.size() > 0 ? st.top() + 1 : 1);
		if(!st.empty()) M[i] = max(M[i], H[st.top()]);
		st.push(i);
	}
	st = stack<int>();
	for(int i = n; i >= 1; i--) {
		while(!st.empty() and H[i] < H[st.top()]) st.pop();
		len[i] = (PS[((int) st.size() > 0 ? st.top() - 1 : n)] - PS[L[i] - 1] + MOD) % MOD;
		if(!st.empty()) M[i] = max(M[i], H[st.top()]);
		st.push(i);
	}
	for(int i = 1; i <= n; i++)
		ans += 1LL * C2(H[i] + 1) * C2(1 + (len[i])) % MOD, ans %= MOD;
	for(int i = 1; i <= n; i++)
		ans -= 1LL * C2(M[i] + 1) * C2(1 + (len[i])) % MOD, ans = (ans + MOD) % MOD;
	cout << ans << '\n';

	return 0;
}
#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...