제출 #1238996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238996		chikien2009	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	56 ms	5832 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n;
long long res, mod = 1e9 + 7, pre[100001], a, b, c, w[100001], h[100001];
set<array<long long, 3>> s;
array<long long, 3> temp;
pair<long long, long long> p[100001];

int main()
{
    setup();

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> h[i];
        p[i] = {h[i], i};
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
        pre[i] = (pre[i - 1] + w[i]) % mod;
    }
    sort(p + 1, p + 1 + n);
    s.insert({n, 1, 0});
    for (int i = 1; i <= n; ++i)
    {
        temp = (*s.lower_bound({p[i].second, -1, -1}));
        s.erase(temp);
        a = (pre[temp[0]] - pre[temp[1] - 1] + mod) % mod;
        a = (a * (a + 1) / 2) % mod;
        b = (p[i].first * (p[i].first + 1) / 2 - temp[2] * (temp[2] + 1) / 2) % mod;
        (res += a * b) %= mod;
        if (p[i].second > temp[1])
        {
            s.insert({p[i].second - 1, temp[1], p[i].first});
        }
        if (p[i].second < temp[0])
        {
            s.insert({temp[0], p[i].second + 1, p[i].first});
        }
    }
    cout << res;
    return 0;
}

• 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