제출 #1124884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124884		nikd	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	67 ms	5192 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int recinta(int N, vector<int> L, vector<int> W){
    const ll md = 1e9+7;
    ll n = (ll) N;
    vector<ll> l, w;
    l.resize(n+2);
    w.resize(n+2);
    l[0] = 0;
    w[0] = 0;
    l[n+1] = 0;
    w[n+1] = 0; 
    for(ll i = 0; i<n; i++){
        l[i+1] = (ll) L[i];
        w[i+1] = (ll) W[i];
    }
    ll sol = 0;
    stack<array<ll, 2>> st;
    ll curr_w = 0;
    for(int i = 0; i<n+2; i++){
        ll x_piccola = curr_w;
        while(!st.empty() && st.top()[0] > l[i]){
            x_piccola = st.top()[1];
            ll hc = st.top()[0];
            ll wtmp = (((curr_w-x_piccola)%md)+md)%md;
            st.pop();
            hc = (hc*(hc+1) %md) * 500000004 %md;
            ll h_basso = max(st.top()[0], l[i]);
            hc -= (h_basso*(h_basso+1) %md) * 500000004 %md;
            hc += md; hc%=md;
            sol += (((wtmp +1)*(wtmp) % md) * hc %md) * 500000004 %md;
        }
        if(st.empty() || st.top()[0] != l[i]){
            st.push({l[i], x_piccola});
        }
        curr_w += w[i];
        curr_w %= md;
    }
    sol %=md;
    return sol;
}

int main(){
    int N;
    cin >> N;

    vector<int> L(N), W(N);

    for(int &x: L) cin >> x;
    for(int &x: W) cin >> x;

    cout << recinta(N, L, W) << "\n";
}

• 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