Submission #1276280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276280		warrenn	Fancy Fence (CEOI20_fancyfence)	C++20	13 / 100	47 ms	9040 KiB

fancyfence

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

const int maxn=1e5;
const int mod=1e9+7;
int h[maxn+2],w[maxn+2],pref[maxn+2];
int n;
vector<pair<int,int> >st;

void build(int idx,int l,int r){
    if(l==r){
        st[idx]={h[l],l};
        return;
    }
    int mid=(l+r)/2;
    build(2*idx,l,mid);
    build(2*idx+1,mid+1,r);
    st[idx]=min(st[2*idx],st[2*idx+1]);
}

pair<int,int> query(int idx,int l,int r,int posl,int posr){
    if(l>posr || r<posl)return {1e18,0};
    if(l>=posl &&r<=posr)return st[idx];
    int mid=(l+r)/2;
    return min(query(2*idx,l,mid,posl,posr),query(2*idx+1,mid+1,r,posl,posr));
}

int mul(int a,int b){
    return (a*b)%mod;
}

int add(int a,int b){
    return (a+b)%mod;
}

int sub(int a,int b){
    int hah=(a-b)%mod;
    return (hah+mod)%mod;
}

int pang(int a,int b){
    if(b==0)return 1;
    int tmp=pang(a,b/2);
    if(b%2==0)return mul(tmp,tmp);
    else return mul(tmp,mul(tmp,a));
}

int ans=0;

void solve(int l,int r,int prv){
    if(l>r)return;
    pair<int,int>apa=query(1,1,n,l,r);
    if(apa.first!=prv){
        int leng=sub(pref[r],pref[l-1]);
        leng=mul(leng,add(leng,1));
       // cout<<leng<<endl;
        leng=mul(leng,pang(2,mod-2));

        ans=add(ans,mul(leng,mul(sub(apa.first,prv),prv+1)));
    }
    
    solve(l,apa.second-1,apa.first);
    solve(apa.second+1,r,apa.first);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    st=vector<pair<int,int>>(4*n+1);

    for(int q=1;q<=n;q++){
        cin>>h[q];
    }
    for(int q=1;q<=n;q++){
        cin>>w[q];
        pref[q]=pref[q-1]+w[q];
    }
    build(1,1,n);
    solve(1,n,0);
    cout<<ans<<endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27