Submission #1282866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282866		lightentheshadow	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	29 ms	3960 KiB

fancyfence

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

const int maxN = 1e5 + 5;
const long long mod = 1e9 + 7;
int h[maxN], w[maxN], L[maxN], R[maxN], belong[maxN];
long long sum = 0, ans = 0, total[maxN];

long long cost(long long X) {
    long long A = X, B = X + 1;
    if (A % 2 == 0) A /= 2;
        else B /= 2;
    A %= mod; B %= mod;
    return (A * B) % mod;
}

void Merge(int u, int v) {
    sum = (sum - cost(total[u]) + mod) % mod;
    sum = (sum - cost(total[v]) + mod) % mod;

    R[u] = R[v]; belong[R[u]] = u;
    total[u] += total[v];
    sum = (sum + cost(total[u])) % mod;
}

long long chain(int l, int r) {
    long long A = 1LL * r * (r + 1) / 2;
    long long B = 1LL * (l - 1) * l / 2;

    return (A - B) % mod;
}

bool cmp(pair<int, int> A, pair<int, int> B) {
    if (A.first != B.first) return A.first > B.first;
    return A.second < B.second;
}

vector<pair<int, int>> event;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        event.push_back({h[i], i});
    }

    for (int i = 1; i <= n; i++)
        cin >> w[i];

    for (int i = 1; i <= n; i++) {
        L[i] = i;
        R[i] = i;
    }

    sort(event.begin(), event.end(), cmp);
    int prev_height = 1e9, i = 0;
    while (i < event.size()) {
        int curr_height = event[i].first;
        ans = (ans + sum * chain(curr_height + 1, prev_height)) % mod;

        while (i < event.size() && curr_height == event[i].first) {
            int p = event[i].second; belong[p] = p; total[p] = w[p]; sum = (sum + cost(w[p])) % mod;
            if (belong[p - 1]) Merge(belong[p - 1], belong[p]);
            if (belong[p + 1]) Merge(belong[p], belong[p + 1]);
            i++;
        }
        prev_height = curr_height;
    }

    ans = (ans + 1LL * sum * chain(1, prev_height)) % mod;
    cout << ans;
    return 0;
}

• 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