Submission #863433

#	Time	Username	Problem	Language	Result	Execution time	Memory
863433		honanhphong	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	74 ms	10860 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int mod = 1e9 + 7;
const int maxn = 1e6;
const int inv = 500000004;
lli h[maxn], w[maxn];
int main()
{
    lli n;
    cin >> n;
    for (lli i = 1; i <= n; i ++)
    {
        cin >> h[i];
    }
    for (lli i = 1; i <= n; i ++)
    {
        cin >> w[i];
    }
    n ++;
    vector<pair<lli,lli>> v;
    v.push_back({0, 0});
	lli ans = 0;
	for(int i = 1; i <= n; i ++)
    {
		lli p = 0;
		while(v.back().first > h[i])
        {
			lli m = max(h[i], v[(int)v.size() - 2].first);
			lli q = v.back().first - m;
			p = (p + v.back().second) % mod;
			v.pop_back();
			ans += (q * (q + 1) % mod * inv % mod + q * m % mod)*(p *(p + 1) % mod * inv % mod) % mod;
			ans %= mod;
		}
		if(v.back().first == h[i])
        {
			v.back().second =(v.back().second + p + w[i]) % mod;
		}else
		{
			v.push_back({h[i], (p + w[i]) % mod});
		}
    }
    cout << ans % mod;
}

• 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