Submission #987284

#	Time	Username	Problem	Language	Result	Execution time	Memory
987284		aykhn	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	93 ms	16472 KiB

fancyfence

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int mod = 1e9 + 7;
 
int add(int a, int b)
{
    a %= mod, b %= mod;
    return (((a + b) % mod) + mod) % mod;
}
int mult(int a, int b)
{
    a %= mod, b %= mod;
    return (((a * b) % mod) + mod) % mod;
}
int sum(int l, int r)
{
    return ((r - l + 1) * (l + r) / 2) % mod;
}
 
int res = 0;
 
struct DSU
{
    int n;
    vector<int> e, val;
    void init(int N)
    {
        n = N;
        e.assign(n + 1, -1);
        val.assign(n + 1, 0);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    void makeval(int x, int y)
    {
        x = get(x);
        val[x] = y;
        res = add(res, val[x] * (val[x] + 1) / 2);
    }
    void unite(int x, int y)
    {
        x = get(x), y = get(y);
        if (x == y) return;
        if (e[x] > e[y]) swap(x, y);
        res = add(res, mult(val[x], val[y]));
        val[x] = add(val[x], val[y]);
        val[y] = 0;
        e[x] += e[y];
        e[y] = x;
    }
};
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int h[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i];
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; i++) mp[h[i]].push_back(i);
    DSU dsu;
    dsu.init(n);
    int ans = 0;
    for (auto it = mp.rbegin(); it != mp.rend(); it++)
    {
        auto &[a, b] = *it;
        for (int i : b) dsu.makeval(i, w[i]);
        for (int i : b) 
        {
            if (i - 1 >= 1 && h[i - 1] >= a) dsu.unite(i, i - 1);
            if (i + 1 <= n && h[i + 1] >= a) dsu.unite(i, i + 1);
        }
        auto it1 = it;
        it1++;
        int nxt = 0;
        if (it1 != mp.rend()) nxt = (*it1).first;
        ans = add(ans, mult(sum(nxt + 1, a), res));
    }
    cout << ans << '\n';
}

• 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