제출 #1238996

#제출 시각아이디문제언어결과실행 시간메모리
1238996chikien2009Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
56 ms5832 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...