Submission #1350946

#TimeUsernameProblemLanguageResultExecution timeMemory
1350946msab3fFancy Fence (CEOI20_fancyfence)C++20
100 / 100
49 ms2764 KiB
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1'000'000'007;
void Add(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
}
int Sum(int a, int b) {
    Add(a, b);
    return a;
}
int Mul(int a, int b) { return 1LL * a * b % MOD; }

const int MAX_N = 100'000 + 10;

int n, par[MAX_N], s, ans;
long long sz[MAX_N];

struct Rect {
    int h, w, i;
    bool operator < (const Rect& other) const {
        return this->h > other.h;
    }
} arr[MAX_N];

int c(long long x) {
    x %= MOD;
    return Mul(Mul(x, Sum(x, +1)), 500000004);
}

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

void unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    par[x] = y;
    Add(s, -c(sz[x]));
    Add(s, -c(sz[y]));
    sz[y] += sz[x];
    Add(s, c(sz[y]));
}

int main() {
    cin >> n;

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

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

    sort(arr + 1, arr + n + 1);

    int p1 = 1, p2 = 1;
    while (p1 <= n) {
        while (p2 <= n && arr[p2].h == arr[p1].h) {
            auto [h, w, i] = arr[p2];
            par[i] = i;
            sz[i] = w;
            Add(s, c(w));
            if (par[i - 1] != 0) unite(i, i - 1);
            if (par[i + 1] != 0) unite(i, i + 1);
            ++p2;
        }
        Add(ans, Mul(s, Sum(c(arr[p1].h), -c(arr[p2].h))));
        p1 = p2;
    }

    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...