oj.uz

Submission #446052

# Submission time Handle Problem Language Result Execution time Memory
446052 2021-07-20T15:00:22 Z Edbert2397 Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 1 ms 332 KB 
/*
~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;
        if(visited[indexx-1] && visited[indexx + 1]){
            // ans += (((sz[find(indexx-1)] + arr[i].se) % mod) * ((sz[find(indexx + 1)] + arr[i].se) % mod) * (arr[i].fi) % mod);
            ans = add(ans,mul((sz[find(indexx-1)] + arr[i].se),mul((sz[find(indexx + 1)] + arr[i].se),count(arr[i].fi + 1))));
            ans %= mod;
            // debug(ans);
            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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct