#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 1e5 + 1, mod = 1e9 + 7;
struct str {
int a, b;
} v[nmax];
vector<pair<int, int>> bag;
int pref[nmax][2];
int suf[nmax][2];
int pw[nmax];
bool f[nmax];
/*
int p2[nmax];
int i2[nmax];
int fast(int N, int E) {
int ans = 1;
while (E) {
if (E & 1) {
ans = (ans * N) % mod;
}
N = (N * N) % mod;
}
return ans;
}
void pre() {
p2[0] = 1;
for (int i = 1; i < nmax; i++) {
p2[i] = (2 * p2[i - 1]) % mod;
}
i2[nmax - 1] = fast(p2[nmax - 1], mod - 2);
for (int i = nmax - 2; i >= 0; i--) {
i2 = (2 * i2[i + 1]) % mod;
}
} */
void pwb(int n) {
for (int i = 1; i <= n; i++) {
pw[i] = 2;
}
}
int32_t main() {
// pre();
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i].a;
}
for (int i = 1; i <= n; i++) {
cin >> v[i].b;
if (v[i].a < v[i].b) {
swap(v[i].a, v[i].b);
}
bag.push_back({v[i].a, i});
bag.push_back({v[i].b, i});
}
sort(bag.begin(), bag.end(), greater<pair<int, int>>());
pwb(n);
int ind = 0;
while (ind < bag.size()) {
vector<pair<int, int>> cr;
cr.push_back(bag[ind++]);
while (ind < bag.size() && cr.back().first == bag[ind].first) {
cr.push_back(bag[ind++]);
}
for (auto [nr, i] : cr) {
pref[i][f[i]] = 1;
for (int j = i - 1; j >= 1; j--) {
pref[i][f[i]] = (pref[i][f[i]] * pw[j]) % mod;
}
suf[i][f[i]] = 1;
for (int j = i + 1; j <= n; j++) {
suf[i][f[i]] = (suf[i][f[i]] * pw[j]);
}
f[i] = 1;
}
for (auto [nr, i] : cr) {
pw[i]--;
}
}
sort(bag.begin(), bag.end());
int ans = 0;
pwb(n);
ind = 0;
for (auto [nr, i] : bag) {
// negativ
int sp = 0, ss = 0;
int prod = 1;
for (int j = i - 1; j >= 1; j--) {
if (v[j].a >= nr) {
sp = (sp + prod * pref[j][0]) % mod;
}
if (v[j].b >= nr) {
sp = (sp + prod * pref[j][1]) % mod;
}
prod = (prod * pw[j]) % mod;
}
prod = 1;
for (int j = i + 1; j <= n; j++) {
if (i == 1) {
cout << i << " " << j << ": " << prod * suf[j][0] << " " << prod * suf[j][0] << '\n';
}
if (v[j].a >= nr) {
ss = (ss + prod * suf[j][0]) % mod;
}
if (v[j].b >= nr) {
ss = (ss + prod * suf[j][1]) % mod;
}
prod = (prod * pw[j]) % mod;
}
pw[i]--;
ans -= (ss * sp) * nr;
cout << i << ": " << ss << " " << sp << '\n';
// cout << "?? " << i << ": " << ss * sp << '\n';
}
cout << "\n\n\n";
pwb(n);
for (int i = 1; i <= n; i++) {
f[i] = 0;
}
sort(bag.begin(), bag.end(), greater<pair<int, int>>());
for (auto [nr, i] : bag) {
// pozitiv
int sp = 0;
int prod = pw[i - 1];
for (int j = i - 2; j >= 1; j--) {
if (v[j].a >= nr) {
sp = (sp + prod * pref[j][0] * (i - j - 1)) % mod;
}
if (v[j].b >= nr) {
sp = (sp + prod * pref[j][1] * (i - j - 1)) % mod;
}
prod = (prod * pw[j]) % mod;
}
int ss = 0;
prod = pw[i + 1];
for (int j = i + 2; j <= n; j++) {
if (v[j].a > nr) {
ss = (ss + prod * suf[j][0] * (j - i - 1)) % mod;
}
if (v[j].b > nr) {
ss = (ss + prod * suf[j][1] * (j - i - 1)) % mod;
}
prod = (prod * pw[j]) % mod;
}
ans += (ss * pref[i][f[i]] + sp * suf[i][f[i]]) * nr;
cout << i << ": " << ss << " " << sp << '\n';
f[i] = 1;
pw[i]--;
}
cout << ans;
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... |