Submission #674790

#	Time	Username	Problem	Language	Result	Execution time	Memory
674790		Iliya	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	32 ms	5068 KiB

fancyfence

#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;
}

• 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