Submission #881387

#	Time	Username	Problem	Language	Result	Execution time	Memory
881387		Alish	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	132 ms	13780 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);


ll mod = 1e9+7;

ll power(ll a, ll b){

    ll ans=1;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;

}


const int N = 1e5+23;
ll pref[N], L[N], R[N];
ll h[N];
ll H[N], W[N], w[N];
int n;


map<pll, int> vis;

ll C(ll n){
    n%=mod;
    return n*(n+1)%mod*power(2, mod-2)%mod;
}


int main()
{
    fast_io
    cin>>n;

    for (int i=1; i<=n; i++) cin>>h[i];
    for (int i=1; i<=n; i++) cin>>w[i];

    for (int i=1; i<=n+1; i++) pref[i]=pref[i-1]+w[i];


    vector<int> st;

    for (int i=1; i<=n; i++){
        while(!st.empty() && h[st.back()]>=h[i]) st.pop_back();
        if(!st.empty()) L[i]=st.back();
        st.pb(i);
    }
    st.clear();

    for (int i=n; i>0; i--){
        while(!st.empty() && h[st.back()]>=h[i]) st.pop_back();
        if(!st.empty()) R[i]=st.back();
        else R[i]=n+1;
        st.pb(i);
    }

    ll ans=0;
    for (int i=1; i<=n; i++){
        if(vis[{h[i], L[i]}]) continue;
        vis[{h[i], L[i]}]=1;
        ll tool=pref[R[i]-1]-pref[L[i]];
        ll r1=h[i]-max(h[R[i]], h[L[i]]);
        ll r2=max(h[R[i]], h[L[i]]);
        ans=(ans+(C(r1)%mod+ r1*r2%mod)%mod*C(tool)%mod)%mod;

    }

    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