Submission #973726

#	Time	Username	Problem	Language	Result	Execution time	Memory
973726		JwFXoiz	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	80 ms	20400 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

#define int long long

const __int128 mod = 1e9 + 7;

__int128 add(__int128 a, __int128 b)
{
    return (((a + b) % mod) + mod) % mod;
}
__int128 mult(__int128 a, __int128 b)
{
    return (((a * b) % mod) + mod) % mod;
}
__int128 sum(__int128 l, __int128 r)
{
    return ((r - l + 1) * (l + r) / 2) % mod;
}

__int128 res = 0;

struct DSU
{
    int n;
    vector<int> e;
    vector<__int128> 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, __int128 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, val[x] * val[y]);
        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;
    __int128 h[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++) 
    {
        int x;
        cin >> x;
        h[i] = x;
    }
    for (int i = 1; i <= n; i++) 
    {
        int x;
        cin >> x;
        w[i] = x;
    }
    map<__int128, vector<int>> mp;
    for (int i = 1; i <= n; i++) mp[h[i]].push_back(i);
    DSU dsu;
    dsu.init(n);
    __int128 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));
    }
    int couT = ans;
    cout << couT << '\n';
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto &[a, b] = *it;
      |               ^

• 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