제출 #1368571

#제출 시각아이디문제언어결과실행 시간메모리
1368571raduvFlooding Wall (BOI24_wall)C++20
100 / 100
393 ms31088 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#pragma GCC target("avx2")
const int MAXN = 500'000;
const int MOD = 1'000'000'007;

int n;
int a[MAXN + 1], b[MAXN + 1], c[MAXN + 1];
int pow2[MAXN + 1];

struct SegTree{
  struct Node{
    int prod, len;
    int pref_sum, suff_sum;
  };
  Node aint[4 * MAXN + 1];
  void build(int node, int st, int dr) {
    if(st == dr) {
      aint[node].len = 1;
      return;
    }
    int mij = (st + dr) / 2;
    build(2 * node, st, mij);
    build(2 * node + 1, mij + 1, dr);
    aint[node].len = aint[2 * node].len + aint[2 * node + 1].len;
  }
  void build() {
    build(1, 1, n);
  }
  void update(int node, int st, int dr, int pos) {
    if(st == dr) {
      aint[node].prod = aint[node].prod + 1;
      aint[node].pref_sum = aint[node].prod;
      aint[node].suff_sum = aint[node].prod;
    }else {
      int mij = (st + dr) / 2;
      if(pos <= mij)
        update(2 * node, st, mij, pos);
      else
        update(2 * node + 1, mij + 1, dr, pos);

      Node &l = aint[2 * node];
      Node &r = aint[2 * node + 1];

      aint[node].prod = (1LL * l.prod * r.prod) % MOD;
      aint[node].pref_sum = (1LL * l.pref_sum * pow2[r.len] + 1LL * l.prod * r.pref_sum) % MOD;
      aint[node].suff_sum = (1LL * l.suff_sum * r.prod + 1LL * r.suff_sum * pow2[l.len]) % MOD;
    }
  }
  void update(int pos) {
    update(1, 1, n, pos);
  }
}segtree;
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;
  sum = (sum - segtree.aint[1].pref_sum + MOD) % MOD;
  sum = (sum - segtree.aint[1].suff_sum + MOD) % MOD;
  sum = (sum + 1LL * segtree.aint[1].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<std::pair<int, int>> v;
  for( int i = 1; i <= n; i++ ) {
    v.push_back({a[i], i});
    v.push_back({b[i], i});
  }
  std::sort(v.begin(), v.end());
  int prev = 0;
  int h = 0;
  while(h < v.size()) {
    sum = (sum + (1LL * compute_sum() * (v[h].first - prev)) % MOD) % MOD;
    int j = h;
    while(j < v.size() && v[j].first == v[h].first) {
      segtree.update(v[j].second);
      j++;
    }

    prev = v[h].first;
    h = j;
  }
  return sum;
}
int main() {
  std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
  read_data();
  precompute_power();
  segtree.build();
  int h_sum = height_total();
  int tot_sum = overall_sum();
  int ans = (h_sum - tot_sum + MOD) % MOD;
  std::cout << ans << "\n";
  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…