Submission #1108575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108575		onlk97	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	38 ms	45040 KiB

fancyfence

#include <bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
using qii=pair <pii,pii>;
const int mod=1e9+7LL;
int h[100010],w[100010];
pii sp[20][100010];
int lg[100010];
pii qry(int ll,int rr){
    int g=lg[rr-ll+1];
    return min(sp[g][ll],sp[g][rr-(1<<g)+1]);
}
int l[100010],r[100010];
int idx[100010],rgl[100010],rgr[100010],curidx;
int dfs1(int tl,int tr){
    if (tl>tr) return 0;
    curidx++;
    int nd=curidx;
    idx[curidx]=qry(tl,tr).y;
    rgl[curidx]=tl; rgr[curidx]=tr;
    l[nd]=dfs1(tl,idx[nd]-1);
    r[nd]=dfs1(idx[nd]+1,tr);
    return nd;
}
int psw[100010];
int ans;
void dfs2(int cur){
    int ch=(h[idx[cur]]+1)%mod*h[idx[cur]]%mod*(mod+1)/2%mod;
    int cw=(psw[rgr[cur]]-psw[rgl[cur]-1]+1+mod)%mod*((psw[rgr[cur]]-psw[rgl[cur]-1]+mod)%mod)%mod*(mod+1)/2%mod;
    if (l[cur]){
        dfs2(l[cur]);
        cw-=(psw[rgr[l[cur]]]-psw[rgl[l[cur]]-1]+1+mod)%mod*((psw[rgr[l[cur]]]-psw[rgl[l[cur]]-1]+mod)%mod)%mod*(mod+1)/2%mod;
        cw%=mod;
        cw+=mod; cw%=mod;
    }
    if (r[cur]){
        dfs2(r[cur]);
        cw-=(psw[rgr[r[cur]]]-psw[rgl[r[cur]]-1]+1+mod)%mod*((psw[rgr[r[cur]]]-psw[rgl[r[cur]]-1]+mod)%mod)%mod*(mod+1)/2%mod;
        cw%=mod;
        cw+=mod; cw%=mod;
    }
    ans+=ch*cw%mod;
    ans%=mod;
}
void solve(){
    int n;
    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; i++) sp[0][i]={h[i],i};
    for (int j=1; (1<<j)<=n; j++){
        for (int i=1; i+(1<<j)-1<=n; i++) sp[j][i]=min(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
    }
    lg[1]=0;
    for (int i=2; i<=n; i++) lg[i]=lg[i/2]+1;
    psw[0]=0;
    for (int i=1; i<=n; i++) psw[i]=(psw[i-1]+w[i])%mod;
    dfs1(1,n);
    dfs2(1);
    cout<<ans<<'\n';
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

• 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