제출 #1301921

#제출 시각아이디문제언어결과실행 시간메모리
1301921cpismylifeOwOFancy Fence (CEOI20_fancyfence)C++20
100 / 100
23 ms11484 KiB
#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

int n;
pair<long long, long long> arr[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x].first;
    }
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x].second;
    }
}

int root;
pair<int, int> child[MaxN];

void BuildTree()
{
    for (int x = 1; x <= n; x++)
    {
        child[x] = make_pair(-1, -1);
    }
    stack<int> st;
    for (int x = 1; x <= n; x++)
    {
        int pre = -1;
        while (!st.empty() && arr[st.top()].first > arr[x].first)
        {
            pre = st.top();
            st.pop();
        }
        child[x].first = pre;
        if (!st.empty())
        {
            child[st.top()].second = x;
        }
        else
        {
            root = x;
        }
        st.push(x);
    }
}

long long val[MaxN];

long long DFS(int u)
{
    long long res = 0, a = (arr[u].first * (arr[u].first + 1) / 2) % mod, b = arr[u].second % mod;
    if (~child[u].first && ~child[u].second)
    {
        res = (res + DFS(child[u].first)) % mod;
        res = (res + DFS(child[u].second)) % mod;
        long long c = (val[child[u].first] + b) % mod, d = (val[child[u].second] + b) % mod;
        res = (res + c * d % mod * a % mod) % mod;
        res = (res - (arr[u].second * (arr[u].second - 1) / 2) % mod * a % mod) % mod;
        val[u] = (c + d - b) % mod;
        return res;
    }
    if (~child[u].first)
    {
        res = DFS(child[u].first);
        long long c = (val[child[u].first] + b) % mod;
        res = (res + c * b % mod * a % mod) % mod;
        res = (res - (arr[u].second * (arr[u].second - 1) / 2) % mod * a % mod) % mod;
        val[u] = c;
        return res;
    }
    if (~child[u].second)
    {
        res = DFS(child[u].second);
        long long c = (val[child[u].second] + b) % mod;
        res = (res + c * b % mod * a % mod) % mod;
        res = (res - (arr[u].second * (arr[u].second - 1) / 2) % mod * a % mod) % mod;
        val[u] = c;
        return res;
    }
    res = (arr[u].second * (arr[u].second + 1) / 2) % mod * a % mod;
    val[u] = b;
    return res;
}

void Exc()
{
    BuildTree();
    long long res = DFS(root);
    cout << (res % mod + mod) % mod;
}

int main()
{
    //freopen("FANCYFENCE.INP", "r", stdin);
    //freopen("FANCYFENCE.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    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...