Submission #1329667

#TimeUsernameProblemLanguageResultExecution timeMemory
1329667dumahaicotFancy Fence (CEOI20_fancyfence)C++20
0 / 100
40 ms488 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 lay(int x)
{
    return x * (x + 1) / 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;
        }
        cout << lay(h[1]) * lay(s);

    }
}
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;
            s = (s % mod + w[i] * 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)
//     {
//         while(!st.empty() && h[st.top()] >= h[i])
//         {
//             s -= w[st.top()] * h[st.top()];
//             sw -= w[st.top()];
//             st.pop();
//         }
//         ans += w[i] * h[i] * (dp[i] - s);
//         ans += w[i] * s;
//         s+= w[i] * h[i];
//         sw+=w[i];
//         st.push(i);
//     }
//     void chay()
//     {
//             FOR(i , 1 , n)
//             {
//                 h[i] = lay(h[i]);
//                 dp[i] = dp[i-1] + w[i];
//             }
//             FOR(i , 1 , n)
//             {
//                 ans = (ans % mod + lay(h[i]) * lay(w[i] % mod) ) % mod;
//             }
//             sw+=w[1];
//             s+=w[1]*h[1];
//             st.push(1);
//             FOR(i , 2 , 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...