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>
using namespace std;
const long long mod=1000000007;
long long twok[500005];
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
pair<long long,long long> arr[n];
for(int i=0; i<n; i++) cin >> arr[i].first;
for(int i=0; i<n; i++) cin >> arr[i].second;
vector<pair<long long,int> > hei;
for(int i=0; i<n; i++){
if(arr[i].first>arr[i].second)swap(arr[i].first,arr[i].second);
hei.push_back({arr[i].first,i});
hei.push_back({arr[i].second,i});
}
sort(hei.begin(),hei.end(),greater<pair<long long,int> >());
long long ans=0;
int st[n],add1[n],add2[n];
memset(add1,0,sizeof(add1));
memset(add2,0,sizeof(add2));
for(int i=0; i<n; i++) st[i]=2;
for(auto [h,i]:hei){
long long mult=1;
for(int j=0; j<i; j++) mult=mult*st[j]%mod;
for(int j=i+1; j<n; j++){
if(h>arr[j].first){
ans+=mult*add1[j]%mod*(h-arr[j].first)%mod;
}
if(h>arr[j].second){
ans+=mult*add1[j]%mod*(h-arr[j].second)%mod;
}
add2[j]+=mult;
if(add2[j]>=mod) add2[j]-=mod;
mult=mult*st[j]%mod;
}
mult=1;
for(int j=i+1; j<n; j++) mult=mult*st[j]%mod;
for(int j=i-1; j>=0; j--){
if(h>arr[j].first){
ans+=mult*add2[j]%mod*(h-arr[j].first)%mod;
}
if(h>arr[j].second){
ans+=mult*add2[j]%mod*(h-arr[j].second)%mod;
}
add1[j]+=mult;
if(add1[j]>=mod) add1[j]-=mod;
mult=mult*st[j]%mod;
}
st[i]--;
}
ans%=mod;
cout << ans;
}
# | 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... |