Submission #1215361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215361		adaawf	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	26 ms	6488 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
struct RECT {
    long long int h, w, num;
} a[100005];
long long int mod = 1e9 + 7, dd[100005], c[100005], p[100005], s[100005], f[100005], h = 0;
bool cmp(RECT aa, RECT bb) {
    return aa.h > bb.h;
}
int Find(int x) {
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
void Merge(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (s[x] > s[y]) swap(x, y);
    p[x] = y;
    s[y] += s[x]; h += c[x] * c[y];
    c[y] += c[x];
    c[y] %= mod;
}
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 >> a[i].h;
        p[i] = i; s[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i].w;
        a[i].num = i; c[i] = a[i].w;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        int k = a[i].num;
        h += a[i].w * (a[i].w + 1) / 2;
        if (dd[k + 1] == 1) {
            Merge(k, k + 1);
        }
        if (dd[k - 1] == 1) {
            Merge(k, k - 1);
        }
        dd[k] = 1;
        h %= mod;
        f[i] = h;
    }
    long long int res = 0;
    for (int i = 1; i <= n; i++) {
        long long int d = a[i].h * (a[i].h + 1) / 2 - a[i + 1].h * (a[i + 1].h + 1) / 2;
        d %= mod;
        res = (res + d * f[i]) % mod;
    }
    cout << res;
}

• 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