Submission #548735

#	Time	Username	Problem	Language	Result	Execution time	Memory
548735		ToroTN	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	49 ms	6680 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
int n,h[100005],w[100005];
int num=0,l,r,lft,rht,cnt;
int node,exist[100005],a[100005];
long long pp=1e9*(1e9+7),sum=0,opt2=0,ans=0,val[100005];
int md=1e9+7;
int opt[100005],headl[1000005],headr[100005];
int value[100005];
vector<pair<int,int> > v;
long long supersum(int a,int b)
{
    return ((long long)(a+b)*(long long)(b-a+1)/2)%(long long)md;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        headl[i]=i;
        headr[i]=i;
        scanf("%d",&h[i]);
        v.push_back({-h[i],i});
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        value[i]=w[i];
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        //printf("%d %d\n",v[i].first,v[i].second);
        if(i==0)
        {
            cnt=1;
        }else
        {
            if(v[i].first!=v[i-1].first)++cnt;
        }
        a[cnt]=-v[i].first;
        node=v[i].second;
        l=value[node-1];
        r=value[node+1];
        lft=node;
        rht=node;
        opt2=w[node];
        if(exist[node-1]!=0)
        {
            opt2+=l;
            opt2%=md;
            sum-=supersum(1,l);
            sum+=pp;
            sum%=md;
            lft=headl[node-1];
        }
        if(exist[node+1]!=0)
        {
            opt2+=r;
            opt2%=md;
            sum-=supersum(1,r);
            sum+=pp;
            sum%=md;
            rht=headr[node+1];
        }
        sum+=supersum(1,opt2);
        sum%=md;
        //printf("%lld\n",sum);
        headr[lft]=rht;
        headl[rht]=lft;
        value[lft]=opt2;
        value[rht]=opt2;
        ++exist[node];
        val[cnt]=sum;
    }
    ans+=(supersum(1,a[cnt]))*val[cnt];
    ans%=md;
    for(int i=cnt-1;i>=1;i--)
    {
        ans-=val[i]*(supersum(a[i]+1,a[i+1]));
        ans+=pp;
        ans%=md;
    }
    printf("%lld\n",ans);
}
/*
5
2 7 4 1 4
3 2 4 2 4
*/
/*
3
1 3 2
2 3 1
*/
/*
5
2 5 1 5 3
2 2 3 2 3
*/

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
fancyfence.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
fancyfence.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d",&h[i]);
      |         ~~~~~^~~~~~~~~~~~
fancyfence.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~

• 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