Submission #682886

#	Time	Username	Problem	Language	Result	Execution time	Memory
682886		lucri	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	98 ms	5348 KiB

fancyfence

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
//ifstream in("intrare.in");
//ofstream out("iesire.out");
long long n,h[100010],w[100010],ans,addans;
stack<pair<long long,long long>>a;
int main()
{
    cin>>n;
    a.push({0,0});
    for(int i=1;i<=n;++i)
        cin>>h[i];
    for(int i=1;i<=n;++i)
    {
        cin>>w[i];
        w[i]+=w[i-1];
    }
    for(int i=1;i<=n;++i)
    {
        while(a.top().first>=h[i])
        {
            long long ws=a.top().second;
            long long hs=a.top().first;
            a.pop();
            if(hs%2==0)
                addans-=(ws-a.top().second)%MOD*hs/2%MOD*(hs+1)%MOD;
            else
                addans-=(ws-a.top().second)%MOD*hs%MOD*(hs+1)/2%MOD;
            if(addans<0)
                addans+=MOD;
        }
        long long sg;
        if((w[i]-w[i-1])%2==0)
            sg=(w[i]-w[i-1])/2%MOD*((w[i]-a.top().second+w[i-1]+1-a.top().second)%MOD)%MOD;
        else
            sg=(w[i]-w[i-1])%MOD*((w[i]-a.top().second+w[i-1]+1-a.top().second)/2%MOD)%MOD;
        if(h[i]%2==0)
        {
            ans+=(addans*((w[i]-w[i-1])%MOD)+sg*h[i]/2%MOD*(h[i]+1)%MOD)%MOD;
            if(ans>=MOD)
                ans-=MOD;
            addans+=(w[i]-a.top().second)%MOD*h[i]/2%MOD*(h[i]+1)%MOD;
            if(addans>=MOD)
                addans-=MOD;
        }
        else
        {
            ans+=(addans*((w[i]-w[i-1])%MOD)+sg*h[i]%MOD*(h[i]+1)/2%MOD)%MOD;
            if(ans>=MOD)
                ans-=MOD;
            addans+=(w[i]-a.top().second)%MOD*h[i]%MOD*(h[i]+1)/2%MOD;
            if(addans>=MOD)
                addans-=MOD;
        }
        a.push({h[i],w[i]});
        //out<<ans<<'\n';
    }
    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