이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mod=1e9+7;
const ll mxN=5e5+5;
ll pw(ll a, ll b){
ll re=1;
for(ll i=0;i<63;i++){
if(b&(1LL<<i)){
re*=a;
re%=mod;
}
a*=a;
a%=mod;
}
return re;
}
ll inv(ll a){
return pw(a, mod-2);
}
ll seg[mxN];
ll lef[mxN][2];
ll rig[mxN][2];
bool good[mxN][2];
ll n;
ll a[mxN][2];
vector<pair<ll, pll>> v;
bool compare(pair<ll, pll> &a, pair<ll, pll> &b){
if(a.F!=b.F){
return a.F>b.F;
}
return a.S.F<b.S.F;
}
bool compare2(pair<ll, pll> &a, pair<ll, pll> &b){
if(a.F!=b.F){
return a.F>b.F;
}
return a.S.F>b.S.F;
}
void solve(){
memset(good, 0, sizeof(good));
cin>>n;
for(ll i=0;i<n;i++){
cin>>a[i][0];
}
for(ll i=0;i<n;i++){
cin>>a[i][1];
}
for(ll i=0;i<n;i++){
v.pb({a[i][0], {i, 0}});
v.pb({a[i][1], {i, 1}});
seg[i]=2;
}
sort(v.begin(), v.end(), compare);
ll ans=0;
for(auto &it:v){
ll val=it.F;
ll id=it.S.F;
ll id2=it.S.S;
ll pre=1;
ll cur=0;
for(ll i=id-1;i>=0;i--){
for(ll j=0;j<2;j++){
if(good[i][j]){
cur+=(((id-i)*pre))*lef[i][j];
cur%=mod;
}
}
pre*=seg[i];
pre%=mod;
}
ll pre2=1;
for(ll i=id+1;i<n;i++){
pre2*=seg[i];
pre2%=mod;
}
ans+=((cur*pre2))*val;
//cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
//cout<<((cur*pre2))*val<<' ';
ans%=mod;
//calculate lef
lef[id][id2]=1;
for(ll i=0;i<id;i++){
lef[id][id2]*=seg[i];
lef[id][id2]%=mod;
}
ans+=((val*lef[id][id2]))*pre2;
//cout<<((val*lef[id][id2]))*pre2<<'\n';
lef[id][id2]=pw(2, id);
ans%=mod;
good[id][id2]=1;
seg[id]--;
}
//cout<<ans<<'\n';
sort(v.begin(), v.end(), compare2);
memset(good, 0, sizeof(good));
for(ll i=0;i<n;i++){
seg[i]=2;
}
for(auto &it:v){
ll val=it.F;
ll id=it.S.F;
ll id2=it.S.S;
ll pre=1;
ll cur=0;
for(ll i=id+1;i<n;i++){
for(ll j=0;j<2;j++){
if(good[i][j]){
cur+=(((i-id)*pre))*rig[i][j];
cur%=mod;
}
}
pre*=seg[i];
pre%=mod;
}
ll pre2=1;
for(ll i=id-1;i>=0;i--){
pre2*=seg[i];
pre2%=mod;
}
ans+=((cur*pre2))*val;
//cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
//cout<<((cur*pre2))*val<<'\n';
ans%=mod;
//calculate rig
rig[id][id2]=pw(2, n-id-1);
/*ans+=((val*rig[id][id2])%mod)*pre2;
ans%=mod;*/
good[id][id2]=1;
seg[id]--;
}
//cout<<ans<<'\n';
memset(good, 0, sizeof(good));
for(ll i=0;i<n;i++){
seg[i]=2;
}
for(auto &it:v){
ll val=it.F;
ll id=it.S.F;
ll id2=it.S.S;
ll pre=1;
ll cur=0;
for(ll i=id+1;i<n;i++){
for(ll j=0;j<2;j++){
if(good[i][j] && a[i][j]==val){
cur+=(((i-id)*pre))*rig[i][j];
cur%=mod;
}
}
pre*=seg[i];
pre%=mod;
}
ll pre2=1;
for(ll i=id-1;i>=0;i--){
pre2*=seg[i];
pre2%=mod;
}
ans-=((cur*pre2))*val;
//cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
//cout<<((cur*pre2))*val<<'\n';
//cout<<cur<<'\n';
ans%=mod;
if(ans<0) ans+=mod;
//calculate rig
//rig[id][id2]=pw(2, n-id-1);
rig[id][id2]=1;
for(ll i=id+1;i<n;i++){
if(a[i][0]==val || a[i][1]==val) rig[id][id2]*=(seg[i]+1);
else rig[id][id2]*=seg[i];
rig[id][id2]%=mod;
}
good[id][id2]=1;
seg[id]--;
}
//cout<<ans<<'\n';
for(ll i=0;i<n;i++){
for(ll j=0;j<2;j++){
ans-=a[i][j]*pw(2, n-1);
ans%=mod;
if(ans<0) ans+=mod;
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
solve();
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... |