제출 #1367157

#제출 시각아이디문제언어결과실행 시간메모리
1367157raditya_noorFancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define ps push
#define pp pop
#define psb push_back
#define ppb pop_back
#define ft front
using namespace std;
const ll mod = 1e9 + 7;

ll expo(ll a, ll b){
    if(b == 1) return a;
    else if(b == 0) return 1;
    else{
        ll x = expo(a, b / 2); x *= x; x %= mod;
        if(b & 1) return (x * a) % mod;
        else return x;
    }
}

ll seq(ll a){
    return (((a * (a + 1)) % mod) * expo(2, mod - 2)) % mod;
}


ll comb_grid(ll a, ll b){
    return (a * b) % mod;
}

int main(){
    int n; cin >> n;
    ll h[n], new_h[n] = {0};
    priority_queue <pair <ll, int>> pq;
    for(int i = 0; i < n; i++){
        cin >> h[i];
        pq.ps({h[i], i});
        new_h[i] = LLONG_MAX;
    }

    ll w[n], new_w[n];
    for(int i = 0; i < n; i++){
        cin >> w[i];
        new_w[i] = 0;
    }

    ll ans = 0;
    int point_l[n]; memset(point_l, -1, sizeof(point_l));
    int point_r[n]; memset(point_r, -1, sizeof(point_r));
    bool done[n] = {0};
    while(!pq.empty()){
        auto [h_now, i] = pq.top(); pq.pop();
        if(!done[i]){
            //find l & r
            int l = i, r = i;
            done[i] = 1;
            ll tot = w[i];
            while(0 <= l - 1 && h[l - 1] == h[i]){
                l--;
                tot += w[l];
                done[l] = 1;
            }
            while(r + 1 < n && h[r + 1] == h[i]){
                r++;
                tot += w[r];
                done[r] = 1;
            }
            
            //update pointer
            int new_l = l, new_r = r;
            while(0 <= new_l - 1 && point_l[new_l - 1] != -1) new_l = point_l[new_l - 1];
            while(new_r + 1 < n && point_r[new_r + 1] != -1) new_r = point_r[new_r + 1];
            point_r[new_l] = new_r;
            point_l[new_r] = new_l;
            
            ll h_min = min({h_now, h[new_r], h[new_l]});

            //ans
            ans += comb_grid(seq(h[i]), seq(tot)), ans %= mod;
            // cout << h[i] << ' ' << tot << ": " << comb_grid(seq(h[i]), seq(tot)) << '\n';
            if(r + 1 < n && done[r + 1]) ans += comb_grid((h_min * new_w[new_r]) % mod, (h_min * tot) % mod), ans %= mod;
            if(0 <= l - 1 && done[l - 1]) ans += comb_grid((h_min * new_w[new_l]) % mod, (h_min * tot) % mod), ans %= mod;
            if((0 <= l - 1 && done[l - 1]) && (r + 1 < n && done[r + 1])) ans += comb_grid((h_min * new_w[new_l]) % mod, (h_min * new_w[new_r]) % mod), ans %= mod;

            //update new_w
            ll w_new_l = new_w[new_l], w_new_r = new_w[new_r];
            new_w[new_l] += tot + w_new_r;
            new_w[new_r] = new_w[new_l];
            
            //update new_h
            new_h[new_l] = h_min;
            new_h[new_r] = h_min;
        }
    }

    cout << ans;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…