Submission #437913

#	Time	Username	Problem	Language	Result	Execution time	Memory
437913		shahriarkhan	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	49 ms	6600 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std ;

const long long mod = 1e9 + 7 , INF = 1e18 ;

int main()
{
    int n ;
    scanf("%d",&n) ;
    long long h[n+3] , w[n+3] , ans = 0 , pref[n+3] = {0} ;
    int left[n+1] = {0} , right[n+1] = {0} , vis[n+1] = {0} ;
    for(int i = 1 ; i <= n ; ++i) scanf("%lld",&h[i]) ;
    for(int i = 1 ; i <= n ; ++i) scanf("%lld",&w[i]) ;
    h[0] = 0 , h[n+1] = 0 ;
    for(int i = 1 ; i <= n ; ++i)
    {
        pref[i] = (pref[i-1] + w[i])%mod ;
    }
    stack<int> L , R ;
    L.push(0) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        while(h[L.top()]>h[i])
        {
            L.pop() ;
        }
        left[i] = L.top() ;
        L.push(i) ;
    }
    R.push(n+1) ;
    for(int i = n ; i >= 1 ; --i)
    {
        while(h[R.top()]>h[i])
        {
            R.pop() ;
        }
        right[i] = R.top() ;
        R.push(i) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        if(vis[i]) continue ;
        while(h[right[i]]==h[i])
        {
            vis[right[i]] = 1 ;
            right[i] = right[right[i]] ;
        }
        long long suf = (pref[right[i]-1] - pref[left[i]] + mod)%mod ;
        long long hj = max(h[left[i]],h[right[i]]) ;
        long long extra1 = ((h[i]*(h[i]+1))/2)%mod ;
        extra1 = (((extra1 - ((hj*(hj+1))/2)%mod)%mod) + mod)%mod ;
        long long extra2 = ((suf*(suf+1))/2)%mod ;
        ans = (ans + (extra1*extra2)%mod)%mod ;
    }
    printf("%lld\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
fancyfence.cpp:12:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(int i = 1 ; i <= n ; ++i) scanf("%lld",&h[i]) ;
      |                                   ~~~~~^~~~~~~~~~~~~~
fancyfence.cpp:13:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(int i = 1 ; i <= n ; ++i) scanf("%lld",&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