Submission #1223890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223890		iamhereforfun	Fancy Fence (CEOI20_fancyfence)	C++20	43 / 100	14 ms	5188 KiB

fancyfence

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int C = 26;
const int LG = 20;
const int R = 25e3 + 5;
const int B = 100;
const int O = 3e5 + 5;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

long long n, h[N], w[N], ans = 0, cur_len = 0, cur_sum = 0, iv = 0;
vector<array<long long, 3>> stk; // height, width, upper part

long long inv(long long a, long long b = MOD - 2)
{
    long long ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        ans %= MOD;
        a %= MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    cin >> n;
    iv = inv(2);
    for (int x = 0; x < n; x++)
    {
        cin >> h[x];
    }
    for (int x = 0; x < n; x++)
    {
        cin >> w[x];
    }
    stk.push_back({0, 0, 0});
    for (int x = 0; x < n; x++)
    {
        while (!stk.empty())
        {
            array<long long, 3> a = stk.back();
            long long ch = a[0], cw = a[1], cd = a[2];
            if (h[x] < ch)
            {
                cur_sum -= (((cur_len - cw) * iv) % MOD) * ((cd * (2 * ch - cd + 1)) % MOD) % MOD;
                cur_sum %= MOD;
                stk.pop_back();
                if (ch - cd > h[x])
                {
                    continue;
                }
                else
                {
                    cur_sum += (((cur_len - cw) * iv) % MOD) * (((2 * h[x] - (h[x] - ch + cd) + 1) * (h[x] - ch + cd)) % MOD) % MOD;
                }
            }
            else
                break;
            cur_sum %= MOD;
        }
        if (cur_sum < 0)
            cur_sum += MOD;
        long long i = 1;
        i *= cur_sum * w[x];
        i %= MOD;
        i += (((w[x] * (w[x] + 1)) % MOD * iv) % MOD) * (((h[x] * (h[x] + 1)) % MOD * iv) % MOD);
        i %= MOD;
        ans += i;
        ans %= MOD;
        i = w[x];
        i *= (((h[x]) * (h[x] + 1)) % MOD * iv) % MOD;
        i %= MOD;
        cur_sum += i;
        cur_sum %= MOD;
        if (stk.back()[0] != h[x])
        {
            stk.push_back({h[x], cur_len, h[x] - stk.back()[0]});
        }
        cur_len += w[x];
        cur_len %= MOD;
        // cout << ans << "\n";
    }
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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