제출 #1363397

#제출 시각아이디문제언어결과실행 시간메모리
1363397takoshanavaFancy Fence (CEOI20_fancyfence)C++20
100 / 100
52 ms5752 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int MOD = 1e9 + 7, N = 1e5 + 5;
int h[N], w[N], par[N], len[N], cur, ans;
bool act[N];

int cnt(int x){
    return (x * (x + 1) / 2) % MOD;
}

int get(int u){
    if(u == par[u]) return u;
    else return par[u] = get(par[u]);
}

void unite(int a, int b){
    a = get(a), b = get(b);
    if(a == b) return;
    cur = (cur - cnt(len[a]) - cnt(len[b])) % MOD;
    if(cur < 0) cur += MOD;
    par[b] = a;
    len[a] = (len[a] + len[b]) % MOD;
    cur = (cur + cnt(len[a])) % MOD;
}
signed main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    for(int i = 0; i < n; i++) cin >> w[i];
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++) v.pb({h[i], i});
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    int i = 0;
    while(i < n){
        int j = i, H = v[i].fs;
        while(j < n and v[j].fs == H) j++;
        for(int k = i; k < j; k++){
            int id = v[k].sc;
            act[id] = 1;
            par[id] = id;
            len[id] = w[id] % MOD;
            cur = (cur + cnt(len[id])) % MOD;
        }
        for(int k = i; k < j; k++){
            int id = v[k].sc;
            if(id > 0 and act[id - 1]) unite(id, id - 1);
            if(id + 1 < n and act[id + 1]) unite(id, id + 1);
        }
        int nxt = (j < n ? v[j].fs : 0);
        int add = (cnt(H) - cnt(nxt)) % MOD;
        if(add < 0) add += MOD;
        ans = (ans + cur * add) % MOD;
        i = j;
    }
    cout << ans % MOD << endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…