Submission #1013726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013726		Luvidi	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	1 ms	860 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*(cw+1)/2;
    sum%=MOD;
    s.insert({1,cw});
    for(auto[x,v]:m){
        ll a=x-pr;
        ans+=sum*(a*(a+1)/2+a*pr);
        ans%=MOD;
        for(auto[l,r]:v){
            auto it=s.upper_bound({l,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});
            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: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27