Submission #1265233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265233		MongHwa	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	0 ms	328 KiB

fancyfence

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define MOD 1000000007

struct A {
    ll h, w;
    int i;

    bool operator< (A& other) {
        if(h != other.h)
            return h > other.h;
        return i < other.i;
    }
};

ll parent[100005];
A arr[100005];
bool chk[100005];

ll dvcq(ll x, int k)
{
    if(k == 1)
        return x;
    ll val = dvcq(x, k/2);
    val = val*val % MOD;
    if(k % 2)
        val = val*x % MOD;
    return val;
}

int find(int x)
{
    if(parent[x] < 0)
        return x;
    parent[x] = find(parent[x]);
    return parent[x];
}

void comb(int a, int b)
{
    a = find(a);
    b = find(b);

    if(a == b)
        return;
    parent[a] += parent[b];
    parent[b] = a;
}

ll getval(ll sz, ll two)
{
    return sz*(sz+1)%MOD * two%MOD;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    ll ans = 0, two = dvcq(2, MOD-2);
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i].h;
        arr[i].i = i;
    }
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i].w;
        parent[i] = -arr[i].w;
        ans += getval(arr[i].h, two)*getval(arr[i].w, two)%MOD;
        ans %= MOD;
    }

    sort(arr, arr+n);
    for(int i = 0; i < n; i++)
    {
        int x = arr[i].i;
        if(x > 0 && chk[x-1])
        {
            ans = (ans - getval(arr[i].h, two)*getval(-parent[find(x)], two)%MOD + MOD) % MOD;
            ans = (ans - getval(arr[i].h, two)*getval(-parent[find(x-1)], two)%MOD + MOD) % MOD;
            comb(x, x-1);
            ans = (ans + getval(arr[i].h, two)*getval(-parent[find(x)], two)%MOD) % MOD;
        }
        if(x+1 < n && chk[x+1])
        {
            ans = (ans - getval(arr[i].h, two)*getval(-parent[find(x)], two)%MOD + MOD) % MOD;
            ans = (ans - getval(arr[i].h, two)*getval(-parent[find(x+1)], two)%MOD + MOD) % MOD;
            comb(x, x+1);
            ans = (ans + getval(arr[i].h, two)*getval(-parent[find(x)], two)%MOD) % MOD;
        }

        chk[x] = 1;
    }

    cout << ans << '\n';
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27