Submission #1015920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015920		Luvidi	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	88 ms	16208 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back
 
void solve() {
    int n;
    cin>>n;
    ll h[n],w[n],MOD=1e9+7;
    for(int i=0;i<n;i++)cin>>h[i];
    for(int i=0;i<n;i++)cin>>w[i];
    ll cw=0;
    map<ll,vector<pll>> m;
    for(int i=0;i<n;i++){
        m[h[i]].pb({cw+1,cw+w[i]});
        cw+=w[i];
    }
    set<pll> s;
    ll pr=0,ans=0,sum=cw%MOD*(cw%MOD+1)/2;
    sum%=MOD;
    s.insert({1,cw});
    for(auto[x,v]:m){
        ll a=x-pr;
        ans+=(a*(a+1)/2+a*pr)%MOD*sum;
        ans%=MOD;
        for(auto[l,r]:v){
            auto it=s.lower_bound({l+1,0});
            it--;
            auto[l2,r2]=*it;
            s.erase(it);
            if(l2<l)s.insert({l2,l-1});
            if(r<r2)s.insert({r+1,r2});
            l%=MOD;
            l2%=MOD;
            r%=MOD;
            r2%=MOD;
            sum-=(r2-l2+1)*(r2-l2+2)/2;
            sum+=(l-l2)*(l-l2+1)/2;
            sum+=(r2-r)*(r2-r+1)/2;
            sum%=MOD;
        }
        pr=x;
    }
    ans+=MOD;
    ans%=MOD;
    cout<<ans<<'\n';
}
 
int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    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