Submission #373469

#	Time	Username	Problem	Language	Result	Execution time	Memory
373469		jenkinsser	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	50 ms	3212 KiB

fancyfence

#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<pii,int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long

using namespace std;

const long long mod = 1000000007;
const int N = 1e5+5;

ll n,ans,h[N],w[N];
vector<int> sections;
int par[N];
bool d[N];

bool f(int x,int y){
    return h[x]>h[y];
}

ll comb2(ll x){
    x%=mod;
    return x*(x-1)/2%mod;
}

ll rec(ll x,ll y){
    return comb2(x+1)*comb2(y+1)%mod;
}

int findSet(int x){
    if(par[x]<0)return x;
    return par[x]=findSet(par[x]);
}

void onion(int x,int y,ll high){
    x=findSet(x);
    y=findSet(y);
    ll h=(rec(high,w[x])+rec(high,w[y]))%mod;
    h=(rec(high,w[x]+w[y])-h+mod)%mod;
    ans=(ans+h)%mod;
    if(par[x]<par[y]){
        par[y]=x;
        w[x]=(w[x]+w[y])%mod;
    }
    else{
        if(par[x]==par[y])
            par[y]--;
        par[x]=y;
        w[y]=(w[x]+w[y])%mod;
    }
}

int32_t main(){
    fastio()
    cin >> n;
    vector<int> vec;
    for0(i,n)
        cin >> h[i];
    for0(i,n){
        cin >> w[i];
        vec.pb(i);
        par[i]=-1;
    }
    sort(vec.begin(),vec.end(),f);
    for0(i,n)
        ans+=rec(h[i],w[i]);
    for(int i:vec){
        if(i!=0&&d[i-1])onion(i-1,i,h[i]);
        if(i!=n-1&&d[i+1])onion(i,i+1,h[i]);
        d[i]=1;
    }
    cout << ans << nl;
}

• 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