Submission #922123

#TimeUsernameProblemLanguageResultExecution timeMemory
922123406Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
27 ms7420 KiB
    #include "bits/stdc++.h"
    #define int long long
    #define FOR(i, a, b) for (int i = (a); i < (b); i++)
    using namespace std;
    const long long INF = 1ll << 60;
    const int N = 1e5 + 5;
    const int M = 1e9 + 7;
    int pw(int a) {
    	a %= M;
    	return a * (a - 1) / 2 % M;
    }
    int H[N], W[N], n, ps[N], lt[N], rt[N];
     
    signed main() {
    	ios::sync_with_stdio(0), cin.tie(0);
    	cin >> n;
    	FOR(i, 1, n + 1) cin >> H[i];
    	FOR(i, 1, n + 1) cin >> W[i];
    	vector<int> st{0};
    	H[0] = H[n + 1] = -INF;
    	FOR(i, 1, n + 1) {
    		while (H[i] < H[st.back()]) st.pop_back();
    		lt[i] = st.back();
    		st.push_back(i);
    	}
    	st = {n + 1};
    	for (int i = n; i >= 1; i--) {
    		while (H[i] <= H[st.back()]) st.pop_back();
    		rt[i] = st.back();
    		st.push_back(i);
    	}
    	FOR(i, 1, n + 1) ps[i] = ps[i - 1] + W[i];
    	int ans = 0;
    	FOR(i, 1, n + 1) {
    		int L = ps[i - 1] - ps[lt[i]] + 1;
    		int R = ps[rt[i] - 1] - ps[i] + 1;
    		int re = pw(L + R + W[i] - 1) - pw(L) - pw(R);
    		ans += re % M * pw(H[i] + 1) % M;
    	}
    	ans %= M;
    	if (ans < 0) ans += M;
    	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...