Submission #866547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
866547	2023-10-26T11:02:16 Z	nima_aryan	Zoltan (COCI16_zoltan)	C++17	140 / 140	116 ms	12992 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	500 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	600 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	69 ms	10120 KB	Output is correct
12	Correct	61 ms	8968 KB	Output is correct
13	Correct	64 ms	8324 KB	Output is correct
14	Correct	80 ms	9004 KB	Output is correct
15	Correct	100 ms	11132 KB	Output is correct
16	Correct	116 ms	12792 KB	Output is correct
17	Correct	90 ms	12992 KB	Output is correct
18	Correct	89 ms	12744 KB	Output is correct
19	Correct	84 ms	12796 KB	Output is correct
20	Correct	90 ms	12740 KB	Output is correct