2022.09.20 PS 일지 (BOJ 19679)

Fancy Fence라는 문제를 풀었다.

스택을 이용한다는 사실을 알고 있었다.

근데 생각보다 알고 있는데도 인덱스 확인하고 설계하는게 좀 까다로웠다.

 

컨디션이 안 좋아서 풀이는 작성 안 하고... 풀 때 끄적인 필기만 캡쳐해서 올리겠다.

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)

const int N = 100003, MOD = 1e9+7;
int n;
ll h[N], w[N], x[N], c[N], sum, ans;
stack<int> s;

ll C(ll n){return (n*(n-1)/2)%MOD;}

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%lld", &h[i]);
    rep(i,1,n) scanf("%lld", &w[i]), x[i] = (x[i-1]+w[i])%MOD;
    rep(i,1,n) {
        while (not empty(s) and h[s.top()] > h[i]) sum = (sum-c[s.top()])%MOD, s.pop();
        ans += (x[i-1]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD*w[i]%MOD;
        ans += sum*w[i]%MOD + C(w[i]+1)*C(h[i]+1)%MOD;
        ans %= MOD;
        c[i] = (x[i]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD;
        sum = (sum+c[i])%MOD;
        s.push(i);
    }
    printf("%lld\n",(ans%MOD+MOD)%MOD);
}