Submission #1223858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223858		iamhereforfun	Fancy Fence (CEOI20_fancyfence)	C++20	Compilation error	0 ms	0 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];
long long cur_sum = 0, cur_len = 0, ans = 0;
vector<array<long long, 3>> stk;

long long cal(long long h, long long w)
{
    long long a = h * (h + 1);
    a %= MOD;
    a *= (w * (w + 1)) % MOD;
    a %= MOD;
    a *= inv(4);
    a %= MOD;
    return a;
}

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;
        a %= MOD;
        ans %= MOD;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    cin >> n;
    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();
            a[0] %= MOD;
            a[1] %= MOD;
            a[2] %= MOD;
            if (a[0] > h[x])
            {
                cur_sum -= ((cur_len - a[2]) * inv(2)) % MOD * (((2 * a[0] - a[1] + 1) * a[1]) % MOD);
                // cout << cur_sum << " " << a[0] << " " << a[1] << " " << a[2] << "\n";
                if (a[0] - a[1] > h[x])
                {
                    stk.pop_back();
                }
                else
                {
                    cur_sum += ((cur_len - a[2]) * inv(2)) % MOD * (((2 * h[x] - (h[x] - a[0] + a[1]) + 1) * (h[x] - a[0] + a[1])) % MOD);
                    stk.pop_back();
                    stk.push_back({h[x], h[x] - a[1], a[2]});
                }
            }
            else
                break;
            cur_sum %= MOD;
        }
        cur_sum %= MOD;
        cur_sum += MOD;
        cur_sum %= MOD;
        if (stk.back()[0] != h[x])
        {
            // cout << x << "\n";
            stk.push_back({h[x], h[x] - stk.back()[0], cur_len});
        }
        // cout << ans << " ";
        // cout << cur_sum << "\n";
        ans += cal(h[x], w[x]) + cur_sum * w[x];
        cur_sum += (w[x] * inv(2)) % MOD * ((h[x] * (h[x] + 1)) % MOD);
        cur_sum %= MOD;
        ans %= MOD;
        cur_len += w[x];
        cur_len %= MOD;
        // cout << ans << " " << cur_sum << "\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;
}

Compilation message (stderr)

fancyfence.cpp: In function 'long long int cal(long long int, long long int)':
fancyfence.cpp:30:10: error: 'inv' was not declared in this scope; did you mean 'int'?
   30 |     a *= inv(4);
      |          ^~~
      |          int