제출 #866547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866547		nima_aryan	Zoltan (COCI16_zoltan)	C++17	140 / 140	116 ms	12992 KiB

zoltan

/**
 *    author:  NimaAryan
 *    created: 2023-10-26 10:49:24  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 M = 1E9 + 7;
void add(i64& a, i64 b) {
  if ((a += b) >= M) {
    a -= M;
  }
}
i64 power(i64 a, i64 b) {
  i64 res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % M;
    }
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}

struct Info {
  int max_lis;
  i64 sum = 0;
};
Info operator+(Info a, Info b) {
  if (a.max_lis == b.max_lis) {
    add(a.sum, b.sum);
  }
  return a.max_lis >= b.max_lis ? a : b;
}

struct Fenwick {
  vector<Info> fenw;
  int n;

  Fenwick(int n) : n(n) {
    fenw.assign(n, Info());
  }

  void modify(int x, Info v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      fenw[i - 1] = fenw[i - 1] + v;
    }
  }
  Info query(int x) {
    Info res{};
    for (int i = x; i > 0; i -= i & -i) {
      res = res + fenw[i - 1];
    }
    return res;
  }
};

auto LIS(vector<int> A) {
  auto B = A;
  sort(B.begin(), B.end());
  int n = A.size();
  for (int i = 0; i < n; ++i) {
    A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
  }
  Fenwick fen(n + 1);  // i -> n-i
  fen.modify(0, Info{0, 1});
  vector<int> lis(n);
  vector<i64> cnt(n);
  for (int i = n - 1; i >= 0; --i) {
    Info best = fen.query(n - A[i]);
    lis[i] = best.max_lis + 1;
    cnt[i] = best.sum;
    fen.modify(n - A[i], Info{lis[i], cnt[i]});
  }
  return pair(lis, cnt);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }
  auto [lis, cnt_lis] = LIS(A);
  for (int i = 0; i < N; ++i) {
    A[i] *= -1;
  }
  auto [lds, cnt_lds] = LIS(A);
  int best = 0;
  for (int i = 0; i < N; ++i) {
    best = max(best, lis[i] + lds[i] - 1);
  }
  i64 cnt = 0;
  for (int i = 0; i < N; ++i) {
    if (lis[i] + lds[i] - 1 == best) {
      add(cnt, cnt_lis[i] * cnt_lds[i] % M * power(2, N - best) % M);
    }
  }
  cout << best << " " << cnt << "\n";
  return 0;
}

• Subtask 1: 140 / 140