Submission #947977

#	Time	Username	Problem	Language	Result	Execution time	Memory
947977		tnknguyen_	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	27 ms	6236 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 

const int MOD = 1e9 + 7;
const int sz = 1e5 + 5;
long long INV;
long long h[sz], w[sz];
long long s[sz], f[sz];

long long bp(long long a, long long b){
    long long ans = 1;
    while(b){
        if(b & 1){
            ans = (ans * a) % MOD;
        }
        a = (a % MOD) * (a % MOD) % MOD;
        b >>= 1;
    }

    return ans;
}

long long c2(long long x){
    return (x * (x+1) % MOD) * (INV % MOD) % MOD;
}

long long add(long long a, long long b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

long long mul(long long a, long long b){
    return (a % MOD) * (b % MOD) % MOD;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);

    int n;
    cin>>n;

    for(int i=1;i<=n;++i){
        cin>>h[i];
    }
    for(int i=1;i<=n;++i){
        cin>>w[i];
        s[i] = (s[i-1] + w[i]) % MOD;
    }
    INV = bp(2, MOD-2);

    stack<int> st; //ascending stack
    st.push(0);
    long long ans = 0;
    for(int i=1;i<=n;++i){
        while(st.size() && h[st.top()] >= h[i]){ //h[st.top()] < h[i]
            st.pop();
        }

        long long len = (s[i] - s[st.top()] + MOD) % MOD;
        long long l1 = (len - w[i] + MOD) % MOD;

        long long A = 0; //equal heights.
        long long B = 0; //smaller heights.

        //# of sub-rect in current section.
        A += mul(c2(h[i]), c2(w[i])); 
        //# of sub-rect of section with height >= h[i] appended to current section.
        A += mul(mul(w[i], l1), c2(h[i])); 
        A %= MOD;

        B += mul(f[st.top()], w[i]);
        B %= MOD;

        f[i] = add(f[st.top()], mul(len, c2(h[i])));

        st.push(i);
        ans = (ans + A + B) % MOD;
    }
    cout<<ans;

    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