제출 #1337918

#제출 시각아이디문제언어결과실행 시간메모리
1337918JungPSFancy Fence (CEOI20_fancyfence)C++20
0 / 100
0 ms344 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=5e8+4;
int get(int a,int b){
    return w[b]-w[a-1];
}

int ans(int x,int y){
    return x%MOD*(x+1LL)%MOD*y%MOD*(y+1LL)%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];

    int ffans=0;
    for(int i=1;i<=n;++i){
        ffans+=ans(w[i],h[i]);
        ffans%=MOD;
    }
    cout << ffans;
    return 0;

    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...