제출 #1223674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223674		iamhereforfun	Fancy Fence (CEOI20_fancyfence)	C++20	30 / 100	14 ms	5192 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) / 2;
    a %= MOD;
    a *= (w * (w + 1) / 2) % MOD;
    return a;
}

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();
            if (a[0] > h[x])
            {
                cur_sum -= cal(a[1], a[2]);
                if (a[0] - a[1] > h[x])
                {
                    stk.pop_back();
                }
                else
                {
                    cur_sum += cal(h[x] - (a[0] - a[1]), a[2]);
                    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_len += w[x];
        cur_len %= MOD;
        if (stk.back()[0] != h[x])
        {
            stk.push_back({h[x], h[x] - stk.back()[0], cur_len});
        }
        ans += cal(h[x], w[x]) + cur_sum * w[x];
        cur_sum += w[x] * ((h[x] * (h[x] + 1) / 2) % MOD);
        cur_sum %= MOD;
        ans %= MOD;
    }
    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: 0 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27