Submission #446058

#	Time	Username	Problem	Language	Result	Execution time	Memory
446058		Edbert2397	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	60 ms	6488 KiB

fancyfence

/*
~2021~
*/
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
#define pii pair<int,int>
#define debug(x) cout << #x << '=' << x << endl;
const int N = 2e5 + 5;
const int INF = 1e9 + 5;
const ll mod = 1e9+7;
ll n,par[N],sz[N],ans,temp[N];
bool visited[N];
struct state{
    int fi,se,idx;
};
state arr[N];
bool cmp(state a,state b){
    if(a.fi == b.fi) return a.se > b.se;
    return a.fi > b.fi;
}
ll sub(ll x,ll y){
    return ((x % mod) - (y % mod) + mod) % mod;
}
ll add(ll x,ll y){
    return ((x % mod) + (y % mod) ) % mod;
}
ll mul(ll x,ll y){
    return ((x % mod) * (y % mod) ) % mod;
}
ll count(ll x){
    // if(x % 2 == 0) return (x/2 * (x-1)) % mod;
    // return ((x-1)/2 * x) % mod;
    ll p=x%mod,q=(x-1)%mod;
    return (((p * q)%mod) * 500000004)%mod;
}

int find(int u){
    if(par[u] == u) return u;
    return par[u] = find(par[u]);
}
void connect(int a,int b){
    if(find(a) == find(b)) return;
    sz[find(a)] += sz[find(b)];
    par[find(b)] = find(a);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(,r,stdin);
    //freopen(,w,stdout);
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>arr[i].fi;
        temp[i] = arr[i].fi;
        arr[i].idx = i;
    }
    for(int i = 1;i<=n;i++){
        cin>>arr[i].se;
        ans = add(ans,mul(count(arr[i].fi + 1),count(arr[i].se + 1)));
        ans %= mod;
    }
    for(int i = 1;i<=n;i++){
        par[i] = i;
        sz[i] = arr[i].se;
    }
    sort(arr + 1,arr + n + 1,cmp); 
    visited[0] = 1;
    visited[n + 1] = 1;
    for(int i = 1;i<=n;i++){
        int indexx = arr[i].idx;
        ll totl = arr[i].se,totr = arr[i].se;
        if(visited[indexx - 1]) totl = sz[find(indexx-1)] + arr[i].se;
        if(visited[indexx + 1]) totr = (sz[find(indexx + 1)] + arr[i].se);
        ans = add(ans,mul(mul(totl,totr),count(arr[i].fi + 1)));
        ans %= mod;
        ans =sub(ans,mul(mul(arr[i].se , arr[i].se),count(arr[i].fi + 1)));
        if(indexx > 1 && visited[indexx-1]) connect(indexx,indexx-1);
        if(indexx < n && visited[indexx + 1]) connect(indexx,indexx + 1);
        visited[indexx] = 1;
    }
    cout<<ans<<endl;
}

• 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