Submission #922123

#	Time	Username	Problem	Language	Result	Execution time	Memory
922123		406	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	27 ms	7420 KiB

fancyfence

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

• 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