Submission #945589

#	Time	Username	Problem	Language	Result	Execution time	Memory
945589		beepbeepsheep	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	46 ms	21924 KiB

fancyfence

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

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;
ll h[maxn],w[maxn];
ll ans;
struct node{
    ll s,e,m;
    ii val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val={0,s};
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val.first=v;
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=min(l->val,r->val);
    }
    ii query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return min(l->query(x,y),r->query(x,y));
    }
}*root;
ll tri(ll x){
    x%=mod;
    return (x*(x+1)/2)%mod;
}
void dnc(ll l, ll r, ll par){
    if (l>r) return;
    ll val,pos;
    tie(val,pos)=root->query(l,r);
    val-=par;
    ans+=(val*par%mod+tri(val))%mod*tri(w[r]-w[l-1]);
    ans%=mod;
    val+=par;
    dnc(l,pos-1,val);
    dnc(pos+1,r,val);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    root=new node(1,n);
    for (int i=1;i<=n;i++){
        cin>>h[i];
        root->upd(i,h[i]);
    }
    for (int i=1;i<=n;i++) cin>>w[i],w[i]+=w[i-1];
    dnc(1,n,0);
    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