Submission #1302127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302127		Taxiradio	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	65 ms	4384 KiB

fancyfence

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

const int M = 1e9+7;

int32_t main() {
	int n; cin >> n;
    vector<int> w , h;
    w.push_back(0);
    h.push_back(0);
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        h.push_back(x);
    }
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        w.push_back(x+w.back());
    }
    w.push_back(w.back());
    h.push_back(0);
    vector<int> l(n+2 ,-1) , r(n+2 ,-1);
    stack<int> s1 , s2;
    s1.push(0);
    for(int i = 1; i <= n; i++){
        while(h[s1.top()] > h[i]){
            s1.pop();
        }
        l[i]=s1.top();
        s1.push(i);
    }
    s2.push(n+1);
    for(int i = n; i >= 1; i--){
        while(h[s2.top()] >= h[i]){
            s2.pop();
        }
        r[i]=s2.top();
        s2.push(i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        //cout << i << " " << l[i] << " " << r[i] << endl;
        int u = max(h[l[i]] , h[r[i]]);
        int v = w[r[i]-1]-w[l[i]];
        v%=M;
        ans+=((v*(v+1)/2)%M)*(((h[i])*(h[i]+1)/2-(u)*(u+1)/2)%M);
        //cout << v << " " << u << " " << h[i] << endl;
        //cout << ans << endl;
        ans%=M;
    }
    cout << ans << endl;
}

• 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