Submission #1329680

#TimeUsernameProblemLanguageResultExecution timeMemory
1329680nguyenkhanghuyFancy Fence (CEOI20_fancyfence)C++20
30 / 100
43 ms1952 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,l,r) for(int i=r;i>=l;i--)
#define FOA(i,a) for(auto &i:a)
#define ld long double
#define pb push_back
#define fi first
#define se second

int n;
const int M = 1e3+5;
const int N = 1e5+5;
const int mod = 1e9 + 7;

int h[N] , w[N];
int P(int a, int b)
{
    if(b == 0) return 1;

    int half = P(a, b / 2);

    if(b % 2 == 0)
        return half * half % mod;
    else
        return half * half % mod * a % mod;
}
int lay(int x)
{
    return (x % mod) * ((x + 1) % mod) % mod * P(2,mod-2) % mod ;
}
namespace sub1
{
    int smt[M*4+5];
    bool check()
    {
        if (n <= 1000) return 1;
        return 0;
    }
    void update(int id , int l , int r , int pos , int x)
    {
        if (l > pos || r < pos)
        {
            return ;
        }
        if(l==r)
        {
            smt[id] = x;
            return;
        }
        int mid = (l+r) >> 1;
        update(id * 2 , l , mid , pos , x);
        update(id * 2 + 1, mid + 1 , r , pos , x);
        smt[id] = min(smt[id*2] , smt[id * 2 + 1]);
    }
    int get(int id ,int l , int r , int u , int v)
    {
        if (l > v || r < u)
        {
            return 1e18;
        }
        if (l>=u && r<=v)
        {
            return smt[id];
        }
        int mid = (l+r) >> 1;
        return min(get(id*2 , l , mid , u , v) , get(id*2+1, mid + 1 , r , u , v));
    }
    void chay()
    {
        FOR(i , 0 , M * 4)
        {
            smt[i] = 1e18;
        }
        FOR(i , 1 , n)
        {
            update(1,1,n,i,h[i]);
        }
        int ans = 0;
        FOR(i , 1 , n)
        {
           ans = (ans % mod + (lay(h[i]) * lay(w[i]) % mod) ) % mod;
        }
        int s = 0;
        FOR(i , 1 , n)
        {
            FOR(j ,  1 , i - 1)
            {
               ans = (ans % mod + w[i] * w[j] % mod * get(1 , 1 , n ,j , i) % mod)% mod;  
            }
        }
        cout << ans;
    }
}
namespace sub2
{
    bool check()
    {
        FOR(i , 2 , n)
        {
            if (h[i]!=h[i-1])
            {
                return 0;
            }
        }
        return 1;
    }
    void chay()
    {
        int s = 0;
        FOR(i , 1 , n)
        {
            s = (s % mod +  w[i] % mod) % mod;
        }
        cout << lay(h[1]) * lay(s) % mod;

    }
}
namespace sub3
{
    bool check()
    {
        FOR(i , 2 , n)
        {
            if (h[i] < h[i-1])
            {
                return 0;
            }
        }
        return 1;
    }
    void chay()
    {
        int ans = 0;
        FOR(i , 1 , n)
        {
           ans = (ans % mod + lay(h[i]) * lay(w[i] % mod) ) % mod;
        }
        int s = 0;
        FOR(i , 1 ,n)
        {
            ans = (ans % mod + w[i] * s % mod) % mod;
            s = (s % mod + w[i] * lay(h[i]) % mod) % mod;
        }
        cout << ans;
    }
}
namespace sub4
{
    stack < int > st;
    int S = 0 , sw = 0 , ans = 0;
    int dp[N];
    void push(int i)
    {
        int curW=w[i]%mod;
        int curH=h[i]%mod;
        while(!st.empty() && h[st.top()]>=h[i]){
            int id=st.top(); st.pop();
            int topH=h[id]%mod;
            int topW=w[id]%mod;
            S=((S % mod - topH * topW % mod) + mod)%mod;
            curW=(curW+topW)%mod;
        }

        ans=(ans % mod + w[i] * S % mod)%mod;

        S=(S% mod + curH * curW % mod)%mod;

        st.push(i);
    }
    void chay()
    {
            FOR(i , 1 , n)
            {
            ans = (ans % mod + lay(h[i]) * lay(w[i] % mod) ) % mod;
            }
            FOR(i , 1 , n)
            {
                push(i);
            }
            cout << ans;
    
    }
}
signed main()
{
    FAST
    cin >> n;
    FOR(i , 1 , n)
    {
        cin >> h[i];
    }
    FOR(i , 1 ,n)
    {
        cin >> w[i];
    }
    if(sub2::check()==1)
    {
        sub2::chay();
        return 0;
    }
    if (sub3::check()==1)
    {
        sub3::chay();
        return 0;
    }
    if (sub1::check()==1)
    {
        sub1::chay() ;
        return 0;
    }
     sub4::chay();

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...