제출 #866522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866522		nima_aryan	Zoltan (COCI16_zoltan)	C++17	14 / 140	85 ms	13304 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& x, i64 y) {
  if ((x += y) >= M) {
    x -= M;
  }
}

template <typename T>
class Fenwick {
 public:
  vector<T> fenw;
  int n;

  Fenwick(int n) : n(n) {
    fenw.resize(n);
  }

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

struct Item {
  int best;
};
Item operator+(Item a, Item b) {
  if (b.best > a.best) {
    swap(a, b);
  }
  return a;
}

auto LIS(const vector<int>& A) {
  int n = A.size();
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) {
    return A[i] > A[j];
  });
  vector<int> lis(n);
  vector<i64> cnt(n);
  Fenwick<Item> fen(n);  // i -> n-i-1 (suffix fenwick)
  vector<i64> sum(n + 1);
  sum[0] = 1;
  for (int i : p) {
    lis[i] = fen.query(n - i).best;
    cnt[i] = sum[lis[i]];
    lis[i] += 1;
    fen.modify(n - i - 1, Item{lis[i]});
    add(sum[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 pow2 = 1;
  int p = 0;
  while (p < N - best) {
    pow2 = (pow2 * 2) % M;
    p += 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 * pow2 % M);
    }
  }
  cout << best << " " << cnt << "\n";
  return 0;
}

• Subtask 1: 14 / 140