Submission #881498

#	Time	Username	Problem	Language	Result	Execution time	Memory
881498		Arshi	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	26 ms	9084 KiB

fancyfence

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb                  push_back
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)

const ll mod = 1e9 + 7;
const int MXN = 2e5 + 4;

ll n, ans;

ll h[MXN], w[MXN], ps[MXN];
ll l[MXN], r[MXN];

ll C(ll x)
{
    ll y = x * (x - 1) / 2;
    return y % mod;
}

ll Sm(ll a, ll b)
{
    return (ps[b] - ps[a] + mod) % mod;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(ll i = 1; i <= n; i ++)
        cin >> h[i];
    for(ll i = 1; i <= n; i ++) {
        cin >> w[i];
        ps[i] = (ps[i - 1] + w[i]) % mod;
    }
    ps[n + 1] = ps[n];

    stack<ll> cnd; cnd.push(0);
    for(ll i = 1; i <= n; i ++) {
        while(cnd.size() && h[i] < h[cnd.top()])
            cnd.pop();
        if(cnd.size())
            l[i] = cnd.top();
        cnd.push(i);
    }
    stack<ll> cdn; cdn.push(0);
    for(ll i = n; i > 0; i --) {
        while(cdn.size() && h[i] <= h[cdn.top()])
            cdn.pop();
        if(cdn.size())
            r[i] = cdn.top();
        cdn.push(i);
    }
    for(ll i = 1; i <= n; i ++)
        if(!r[i])
            r[i] = n + 1;

    for(ll i = 1; i <= n; i ++) {
        ll hs = C(h[i] + 1);
        ll x = (Sm(i, r[i] - 1) + 1) % mod;
        ll y = (Sm(l[i], i - 1) + 1) % mod;
        ll tmp = x * y % mod;
        ll z = (w[i] - 1) * x % mod;
        ll t = (w[i] - 1) * y % mod;
        ll o = C(w[i] - 1);
        tmp = (tmp + z + t + o) % mod;
        ans = (ans + tmp * hs % mod) % mod;
        //cout << i << ' ' << x << '\n';
    }

    cout << ans;

    return 0;
}

/*!
ahkh
*/

• 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