oj.uz

답안 #865692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865692 2023-10-24T14:09:48 Z boris_mihov Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 2 ms 4700 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n;
int h[MAXN];
int w[MAXN];
int prev[MAXN];
int next[MAXN];
llong prefix[MAXN];
std::stack <int> st;
void solve()
{  
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + w[i];
    } 

    h[0] = h[n + 1] = INF;
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (h[st.top()] > h[i])
        {
            st.pop();
        }

        prev[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();
    st.push(n + 1);

    for (int i = n ; i >= 1 ; --i)
    {
        while (h[st.top()] >= h[i])
        {
            st.pop();
        }

        next[i] = st.top();
        st.push(i);
    }

    llong ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        llong cntPrev = (prefix[i] - prefix[prev[i]]) % MOD;
        llong cntNext = (prefix[next[i] - 1] - prefix[i] + 1) % MOD;
        ans += ((cntPrev * cntNext) % MOD) * h[i];
        ans %= MOD;
    }

    std::cout << ans << '\n';
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> h[i];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> w[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -