제출 #1219031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219031		thunopro	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1 ms	328 KiB

fancyfence

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

const long long MOD = 1'000'000'007LL;
const long long INV2 = 500'000'004LL;          // 2^(-1) mod MOD

struct DSU {
    vector<int> p;             // parent (-size for root)
    vector<long long> len;     // tổng bề rộng thật của run
    DSU(int n): p(n, -1), len(n, 0) {}
    int find(int x){ return p[x] < 0 ? x : p[x] = find(p[x]); }
};

inline long long addmod(long long a, long long b){
    a += b;
    if(a >= MOD) a -= MOD;
    return a;
}
inline long long submod(long long a, long long b){
    a -= b;
    if(a < 0) a += MOD;
    return a;
}
inline long long mulmod(long long a, long long b){
    return (a % MOD) * (b % MOD) % MOD;
}
inline long long choose2(long long L){                // (L+1 choose 2) mod MOD
    return mulmod(mulmod(L % MOD, (L + 1) % MOD), INV2);
}
// ∑_{k=lo}^{hi} k   (lo< =hi)  mod MOD
inline long long sumRange(long long lo, long long hi){
    long long sHi = mulmod(hi % MOD, (hi + 1) % MOD);
    long long sLo = mulmod(lo % MOD, (lo + 1) % MOD);
    return mulmod(submod(sHi, sLo), INV2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if(!(cin >> N)) return 0;

    vector<long long> h(N), w(N);
    for(auto &x: h) cin >> x;
    for(auto &x: w) cin >> x;

    /* sắp đoạn theo chiều cao giảm dần */
    vector<pair<long long,int>> ord;
    ord.reserve(N);
    for(int i = 0; i < N; ++i) ord.push_back({h[i], i});
    sort(ord.rbegin(), ord.rend());

    DSU dsu(N);
    vector<char> active(N, 0);
    long long F = 0;               // tổng (runWidth+1 choose 2) hiện thời
    long long ans = 0;

    long long prevH = ord.empty() ? 0 : ord[0].first + 1;
    size_t pos = 0;

    while(pos < ord.size()){
        long long curH = ord[pos].first;

        /* 1. đóng góp cho mọi k trong (curH, prevH] */
        if(prevH > curH){
            long long sumK = sumRange(curH, prevH - 1);
            ans = mulmod(ans + F * sumK % MOD, 1);     // giữ mod
        }

        /* 2. kích hoạt các đoạn cao = curH */
        while(pos < ord.size() && ord[pos].first == curH){
            int idx = ord[pos].second;
            active[idx] = 1;
            dsu.len[idx] = w[idx];

            F = addmod(F, choose2(w[idx]));            // run mới

            auto tryMerge = [&](int u, int v){
                if(v < 0 || v >= N || !active[v]) return;
                u = dsu.find(u); v = dsu.find(v);
                if(u == v) return;
                long long L1 = dsu.len[u], L2 = dsu.len[v];

                F = submod(F, choose2(L1));
                F = submod(F, choose2(L2));

                /* gộp v vào u */
                dsu.p[u] += dsu.p[v];
                dsu.p[v] = u;
                dsu.len[u] = L1 + L2;

                F = addmod(F, choose2(dsu.len[u]));
            };
            tryMerge(idx, idx - 1);
            tryMerge(idx, idx + 1);

            ++pos;
        }
        prevH = curH;
    }

    /* 3. dải còn lại k = 1 .. prevH */
    if(prevH){
        long long sumK = sumRange(0, prevH - 1);       // 0..prevH-1  ⇒ 1..prevH
        ans = (ans + F * sumK) % MOD;
    }

    cout << ans % MOD << '\n';
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27