Submission #492484

#	Time	Username	Problem	Language	Result	Execution time	Memory
492484		LittleCube	Fancy Fence (CEOI20_fancyfence)	C++14	30 / 100	82 ms	5848 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll MOD = 1000000007;
const ll inv2 = 500000004;

int N;
ll h[100005], w[100005], ans;
vector<pll> mono = {pll{0, 0}};

signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> h[i];
    for (int i = 1; i <= N; i++)
        cin >> w[i];
    N++;
    for (int i = 1; i <= N; i++)
    {
        if (mono.empty())
            mono.emplace_back(pll{h[i], w[i]});
        else
        {
            while (h[i] < mono.back().F)
            {
                ans = (ans + (((((mono.back().S * (mono.back().S + 1) % MOD) * inv2 % MOD) * (mono[mono.size() - 1].F - mono[mono.size() - 2].F) % MOD) * (mono[mono.size() - 1].F + mono[mono.size() - 2].F + 1) % MOD) * inv2 % MOD)) % MOD;
                pll p = mono.back();
                mono.pop_back();
                mono.back().S = (mono.back().S + p.S) % MOD;
            }
            if (h[i] == mono.back().F)
                mono.back().S = (mono.back().S + w[i]) % MOD;
            else
                mono.emplace_back(pll{h[i], w[i]});
        }
        
    }
    cout << ans << '\n';
}

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