Submission #749011

#	Time	Username	Problem	Language	Result	Execution time	Memory
749011		bgnbvnbv	Fancy Fence (CEOI20_fancyfence)	C++14	12 / 100	1 ms	468 KiB

fancyfence

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll get(ll l,ll r)
{
    if(r<l) return 0;
    ll sum=(r+l);
    ll cnt=(r-l+1);
    if(sum%2==0) sum/=2;
    else cnt/=2;
    return sum*cnt%mod;
}
ll n,h[maxN];
deque<int> dq;
vector<pli>vec;
ll l[maxN],r[maxN],w[maxN],low[maxN],high[maxN];
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=n;i++) cin >> w[i];
    ll last=0;
    for(int i=1;i<=n;i++)
    {
        low[i]=last+1;
        high[i]=last+w[i];
        last+=w[i];
        low[i]%=mod;
        high[i]%=mod;
    }
    low[n+1]=last+1;
    low[n+1]%=mod;
    high[0]=0;
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty()&&h[i]<=h[dq.back()]) dq.pop_back();
        if(dq.size()) l[i]=dq.back();
        else l[i]=0;
        vec.emplace_back(h[i],i);
        dq.pb(i);
    }
    dq.clear();
    ll ans=0;
    ll sum=0;
    for(int i=n;i>=1;i--)
    {
        while(!dq.empty()&&h[i]<h[dq.back()]) dq.pop_back();
        if(dq.size()) r[i]=dq.back();
        else r[i]=n+1;
        ans+=h[i]*(high[i]-high[l[i]])%mod*(low[r[i]]-high[i])%mod;
        ans+=h[i]*get(low[i],high[i]-1)%mod-h[i]*high[l[i]]%mod*(high[i]-low[i])%mod;
        ans%=mod;
        if(ans<0) ans+=mod;
        sum+=(high[i]-high[l[i]])*(low[r[i]]-high[i])%mod;
        sum+=get(low[i],high[i]-1)-high[l[i]]*(high[i]-low[i])%mod;
        sum%=mod;
        if(sum<0) sum+=mod;
        dq.pb(i);
    }
    ll vc=ans;
    sort(vec.begin(),vec.end());
    ll cur=0;
    for(int i=0;i<vec.size();i++)
    {
        ans+=(vec[i].first-cur)*vc%mod-get(1,vec[i].first-cur)*sum%mod;
        vc-=(vec[i].fi-cur)*sum%mod;
        ans=ans%mod;
        if(ans<0) ans+=mod;
        vc%=mod;
        if(vc<0) vc+=mod;
        ll x=vec[i].se;
        sum-=(high[x]-high[l[x]])*(low[r[x]]-high[x])%mod;
        sum-=get(low[x],high[x]-1)-high[l[x]]*(high[x]-low[x])%mod;
        sum%=mod;
        if(sum<0) sum+=mod;
        cur=vec[i].fi;
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

fancyfence.cpp: In function 'void solve()':
fancyfence.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27