結果

問題 No.1975 Zigzag Sequence
ユーザー ChanyuhChanyuh
提出日時 2022-06-27 22:46:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 113 ms / 2,000 ms
コード長 7,289 bytes
コンパイル時間 1,651 ms
コンパイル使用メモリ 138,768 KB
実行使用メモリ 22,552 KB
最終ジャッジ日時 2024-11-20 06:18:27
合計ジャッジ時間 5,625 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,600 KB
testcase_01 AC 4 ms
9,728 KB
testcase_02 AC 4 ms
9,600 KB
testcase_03 AC 12 ms
10,880 KB
testcase_04 AC 7 ms
10,112 KB
testcase_05 AC 97 ms
19,948 KB
testcase_06 AC 63 ms
15,472 KB
testcase_07 AC 15 ms
10,920 KB
testcase_08 AC 60 ms
15,324 KB
testcase_09 AC 96 ms
20,344 KB
testcase_10 AC 64 ms
15,124 KB
testcase_11 AC 75 ms
19,476 KB
testcase_12 AC 21 ms
11,948 KB
testcase_13 AC 5 ms
9,600 KB
testcase_14 AC 4 ms
9,516 KB
testcase_15 AC 4 ms
9,728 KB
testcase_16 AC 6 ms
9,644 KB
testcase_17 AC 4 ms
9,600 KB
testcase_18 AC 71 ms
19,688 KB
testcase_19 AC 67 ms
19,692 KB
testcase_20 AC 73 ms
19,908 KB
testcase_21 AC 73 ms
19,908 KB
testcase_22 AC 77 ms
22,424 KB
testcase_23 AC 77 ms
22,476 KB
testcase_24 AC 90 ms
22,552 KB
testcase_25 AC 85 ms
22,292 KB
testcase_26 AC 98 ms
20,092 KB
testcase_27 AC 113 ms
21,204 KB
testcase_28 AC 81 ms
22,428 KB
testcase_29 AC 81 ms
22,428 KB
testcase_30 AC 83 ms
22,424 KB
testcase_31 AC 82 ms
22,420 KB
testcase_32 AC 67 ms
19,912 KB
testcase_33 AC 67 ms
19,908 KB
testcase_34 AC 103 ms
20,280 KB
testcase_35 AC 101 ms
20,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <ciso646>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i >= 0; i--)
#define Rep(i, sta, n) for (int i = sta; i < n; i++)
#define Per(i, sta, n) for (int i = n - 1; i >= sta; i--)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;

template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

template <int mod>
struct ModInt {
  long long x;
  static constexpr int MOD = mod;

  ModInt() : x(0) {}
  ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  explicit operator int() const { return x; }

  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  ModInt operator%(const ModInt &p) const { return ModInt(0); }

  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return ModInt(u);
  }

  ModInt power(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  ModInt power(const ModInt p) const { return ((ModInt)x).power(p.x); }

  friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
    return os << p.x;
  }
  friend istream &operator>>(istream &is, ModInt<mod> &a) {
    long long x;
    is >> x;
    a = ModInt<mod>(x);
    return (is);
  }
};

using modint = ModInt<mod>;

template <class S, S (*op)(S, S), S (*e)()>
struct SegmentTree {
 public:
  SegmentTree() : SegmentTree(0) {}
  SegmentTree(int n) : SegmentTree(std::vector<S>(n, e())) {}
  SegmentTree(const std::vector<S> &v) : _n(int(v.size())) {
    log = ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }

  void set_val(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  S get(int p) {
    assert(0 <= p && p < _n);
    return d[p + size];
  }

  S query(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;

    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }

  S all_query() { return d[1]; }

  template <bool (*f)(S)>
  int max_right(int l) {  // f(op([l,r)))==trueを満たす最大のr
    return max_right(l, [](S x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) {
    assert(0 <= l && l <= _n);
    assert(f(e()));
    if (l == _n) return _n;
    l += size;
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < size) {
          l = (2 * l);
          if (f(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(S)>
  int min_left(int r) {  // f(op([l,r)))==trueを満たす最小のl
    return min_left(r, [](S x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) {
    assert(0 <= r && r <= _n);
    assert(f(e()));
    if (r == 0) return 0;
    r += size;
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (f(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  int _n, size, log;
  std::vector<S> d;

  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }

  int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
  }
};

template <typename T>
struct Compress {
  vector<T> V;

  Compress() { V.clear(); }
  Compress(vector<T> &V) : V(V) {}

  void add(T x) { V.push_back(x); }

  int build() {
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    return V.size();
  }

  int get(T x) {  // get the index of the minimum element which is greater than
                  // x
    return lower_bound(V.begin(), V.end(), x) - V.begin();
  }

  pair<int, int> section(T l, T r) {  // get the range of indexes of [l,r)
    int l_ = get(l), r_ = get(r);
    return pair<int, int>(l_, r_);
  }

  T &operator[](int i) { return V[i]; };
};

int n, a[200010];
modint pow2[200010];
vector<int> v[200010];

modint F(modint a, modint b) { return a + b; }
modint e() { return 0; }

void solve() {
  cin >> n;
  Compress<int> comp;
  rep(i, n) {
    cin >> a[i];
    comp.add(a[i]);
  }
  pow2[0] = 1;
  rep(i, n) pow2[i + 1] = pow2[i] * 2;
  int m = comp.build();
  rep(i, n) v[comp.get(a[i])].push_back(i);
  SegmentTree<modint, F, e> seg1(n), seg2(n), seg3(n), seg4(n);
  modint ans = 0;
  rep(i, m) {
    for (int t : v[i]) {
      ans += seg1.query(0, t) * seg2.query(t + 1, n);
    }
    for (int t : v[i]) {
      seg1.set_val(t, pow2[t]);
      seg2.set_val(t, pow2[n - 1 - t]);
    }
  }
  per(i, m) {
    for (int t : v[i]) {
      ans += seg3.query(0, t) * seg4.query(t + 1, n);
    }
    for (int t : v[i]) {
      seg3.set_val(t, pow2[t]);
      seg4.set_val(t, pow2[n - 1 - t]);
    }
  }
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(50);
  solve();
}
0