Submission #1337943

#TimeUsernameProblemLanguageResultExecution timeMemory
1337943JungPSFancy Fence (CEOI20_fancyfence)C++20
30 / 100
59 ms12148 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
int h[100007],w[100007];
int l[100007],r[100007];
map<int,int> mx;
const int MOD=1e9+7;
const int INV2=(MOD+1)/2;
int get(int a,int b){
    return w[b]-w[a-1];
}

int ans(int x,int y){
    return x%MOD*(x+1)%MOD*y%MOD*(y+1)%MOD*INV2%MOD*INV2%MOD;
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n; cin >> n;
    for(int i=1;i<=n;++i) cin >> h[i];
    for(int i=1;i<=n;++i) cin >> w[i],w[i]+=w[i-1],w[i]%=MOD;
    stack<int> st;
    for(int i=1;i<=n;++i){
        while(!st.empty() && h[st.top()]>=h[i]) st.pop();
        if(st.empty()) l[i]=1;
        else l[i]=st.top()+1;
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i=n;i>=1;--i){
        while(!st.empty() && h[st.top()]>=h[i]) st.pop();
        if(st.empty()) r[i]=n;
        else r[i]=st.top()-1;
        st.push(i);
    }
    vector<pair<int,pair<int,int>>> toprocess;
    for(int i=1;i<=n;++i){
        int bounda=get(1,l[i]-1)+1;
        int boundb=get(1,r[i]);
        int ha=h[i];
        if(boundb==mx[ha]) continue;
        mx[ha]=max(mx[ha],boundb);
        toprocess.push_back({ha,{bounda,boundb}});
        //cout << bounda << " " << boundb << " " << ha << endl;
        //cout << ans(boundb-bounda+1,ha)-ans(boundb-bounda+1,prev) << endl;
    }
    int fans=0;
    int prev=0;
    sort(toprocess.begin(),toprocess.end());
    for(int i=0;i<toprocess.size();++i){
        if(i!=0 && toprocess[i].first!=toprocess[i-1].first){
            prev=toprocess[i-1].first;
        }
        fans+=ans(toprocess[i].second.second-toprocess[i].second.first+1,toprocess[i].first);
        fans-=ans(toprocess[i].second.second-toprocess[i].second.first+1,prev);
        fans+=MOD;
        fans%=MOD;
        
    }
    cout << fans;
}
#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...