Submission #1368569

#TimeUsernameProblemLanguageResultExecution timeMemory
1368569raduvFlooding Wall (BOI24_wall)C++20
70 / 100
5094 ms12160 KiB
#include <bits/stdc++.h>
const int MAXN = 500'000;
const int MOD = 1'000'000'007;
/*
voi folosi formula :
S(h) = n * 2 ^ n - sum{prod{k <= i, c_k} * 2 ^ (n - i)}
                 - sum{prod{k >= i, c_k} * 2 ^ (i - 1)}
                 + n * prod{c_i}

unde c_i = (a_i < h + b_i < h)

voi face brutul in O(n ^ 2) mai intai, pentru fiecare H voi calcula S(h)

*/
int n;
int a[MAXN + 1], b[MAXN + 1], c[MAXN + 1];
int pow2[MAXN + 1];
void read_data() {
  std::cin >> n;
  for( int i = 1; i <= n; i++ )
    std::cin >> a[i];
  for( int i = 1; i <= n; i++ )
    std::cin >> b[i];
}
void precompute_power() {
  pow2[0] = 1;
  for( int i = 1; i <= n; i++ )
    pow2[i] = 2 * pow2[i - 1] % MOD;
}
int compute_sum() {
  int sum = 0;
  sum = 1LL * n * pow2[n] % MOD;


  int prod = 1;
  for( int i = 1; i <= n; i++ ) {
    prod = 1LL * prod * c[i] % MOD;
    sum = (sum - (1LL * prod * pow2[n - i]) % MOD + MOD) % MOD;
  }
  prod = 1;
  for( int i = n; i >= 1; i-- ) {
    prod = 1LL * prod * c[i] % MOD;
    sum = (sum - (1LL * prod * pow2[i - 1]) % MOD + MOD) % MOD;
  }
  sum = (sum + 1LL * prod * n) % MOD;
  return sum;
}
int overall_sum() {
  int sum = 0;
  for( int i = 1; i <= n; i++ ) {
    sum = (sum + 1LL * (a[i] + b[i]) * pow2[n - 1]) % MOD;
  }
  return sum;
}
int height_total() {
  int sum = 0;
  std::vector<int> v;
  for( int i = 1; i <= n; i++ ) {
    v.push_back(a[i]);
    v.push_back(b[i]);
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  int prev = 0;
  for( int h = 0; h < v.size(); h++ ) {
    sum = (sum + (1LL * compute_sum() * (v[h] - prev)) % MOD) % MOD;
    for( int i = 1; i <= n; i++ ) {
      if(a[i] == v[h])
        c[i]++;
      if(b[i] == v[h])
        c[i]++;
    }
    prev = v[h];
  }
  return sum;
}
int main() {
  read_data();
  precompute_power();
  int h_sum = height_total();
  int tot_sum = overall_sum();
  int ans = (h_sum - tot_sum + MOD) % MOD;
  std::cout << ans << "\n";
  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...