Submission #1287372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287372		Davdav1232	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	73 ms	2768 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;

const ll MOD=1e9+7;
vll h, w, subsum;
ll ans=0;

void solve(int l, int r){
    if(r<=l+1) return;
    int m=(l+r)/2;
    solve(l, m);
    solve(m, r);
    //now solve for segments between!!
    //if the h on the right side is strictly smaller:
    ll mini1=MOD;
    for(int i=m, j=m; j<r;){
        mini1=min(mini1, h[j]);
        while(i-1>=l && h[i-1]>mini1) i--;
        ans+=((((subsum[m]-subsum[i]+MOD)%MOD)*(w[j]))%MOD)*((((mini1*mini1+mini1)/2)%MOD)%MOD);
        ans%=MOD;
        j++;
    }
    mini1=MOD;
    for(int i=m-1, j=m-1; i>=l;){
        mini1=min(mini1, h[i]);
        while(j+1<r && h[j+1]>=mini1) j++;
        ans+=((((subsum[j+1]-subsum[m]+MOD)%MOD)*w[i])%MOD)*(((mini1*mini1+mini1)/2)%MOD);
        ans%=MOD;
        i--;
    }
}




int main(){
    int n;
    cin>>n;
    h.resize(n);
    w.resize(n);
    subsum.assign(n+1, 0);
    for(int i=0; i<n; i++) cin>>h[i];
    for(int i=0; i<n; i++) cin>>w[i];
    for(int i=0; i<n; i++) subsum[i+1]=(subsum[i]+w[i])%MOD;
    for(int i=0; i<n; i++){
        ans+=(((h[i]*h[i]+h[i])/2)%MOD)*(((w[i]*w[i]+w[i])/2)%MOD);
        ans%=MOD;
    }
    bool works=1;
    for(int i=0; i+1<n; i++) if(h[i]>h[i+1]) works=0;
    if(works){
    for(int i=0; i<n; i++){
        ans+=((w[i]*(((h[i]*h[i]+h[i])/2)%MOD))%MOD)*(subsum[n]-subsum[i+1]+MOD);
        ans%=MOD;
    }}


    if(!works) solve(0, n);
    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