This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N = 2e5 + 5;
const int K = 20;
const int mod = 1e9 + 7;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin>>n;
set<int> dfvals;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++){
cin>>a[i];
dfvals.insert(a[i]);
}
for(int i = 0; i < n; i++){
cin>>b[i];
dfvals.insert(b[i]);
}
int ans = 0;
vector<vector<int> > pre(n+1, vector<int>(3)), suf(n+1, vector<int>(3)); // 0 => max < itr, 1 => max = itr, 2 => max > itr
for(auto itr: dfvals){
pre[0][0] = 1;
pre[0][1] = pre[0][2] = 0;
for(int i = 0; i < n; i++){
pre[i+1][0] = pre[i+1][1] = pre[i+1][2] = 0;
if(a[i] < itr){
pre[i+1][0] += pre[i][0];
pre[i+1][1] += pre[i][1];
pre[i+1][2] += pre[i][2];
}
else if(a[i] == itr){
pre[i+1][1] += pre[i][0];
pre[i+1][1] += pre[i][1];
pre[i+1][2] += pre[i][2];
}
else{
pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
}
for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;
if(b[i] < itr){
pre[i+1][0] += pre[i][0];
pre[i+1][1] += pre[i][1];
pre[i+1][2] += pre[i][2];
}
else if(b[i] == itr){
pre[i+1][1] += (pre[i][0] + pre[i][1]);
pre[i+1][2] += pre[i][2];
}
else{
pre[i+1][2] += (pre[i][0] + pre[i][1] + pre[i][2]);
}
for(int j = 0; j < 3; j++) pre[i+1][j] %= mod;
}
suf[n][0] = 1;
suf[n][1] = suf[n][2] = 0;
for(int i = n-1; i >= 0; i--){
suf[i][0] = suf[i][1] = suf[i][2] = 0;
if(a[i] < itr){
suf[i][0] += suf[i+1][0];
suf[i][1] += suf[i+1][1];
suf[i][2] += suf[i+1][2];
}
else if(a[i] == itr){
suf[i][1] += suf[i+1][0];
suf[i][1] += suf[i+1][1];
suf[i][2] += suf[i+1][2];
}
else{
suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
}
for(int j = 0; j < 3; j++) suf[i][j] %= mod;
if(b[i] < itr){
suf[i][0] += suf[i+1][0];
suf[i][1] += suf[i+1][1];
suf[i][2] += suf[i+1][2];
}
else if(b[i] == itr){
suf[i][1] += suf[i+1][0];
suf[i][1] += suf[i+1][1];
suf[i][2] += suf[i+1][2];
}
else{
suf[i][2] += (suf[i+1][0] + suf[i+1][1] + suf[i+1][2]);
}
for(int j = 0; j < 3; j++) suf[i][j] %= mod;
}
int add = 0;
for(int i = 1; i < n-1; i++){
int calc = (pre[i][1] * suf[i+1][1] + pre[i][2] * suf[i+1][1] + pre[i][1] * suf[i+1][2])%mod;
int tot = max(0LL, itr - a[i]) + max(0LL, itr - b[i]);
add = (add + (calc * tot)%mod)%mod;
}
ans = (ans + add)%mod;
}
cout<<ans<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |