oj.uz

Submission #866522

# Submission time Handle Problem Language Result Execution time Memory
866522 2023-10-26T10:14:10 Z nima_aryan Zoltan (COCI16_zoltan) C++17
14 / 140
 85 ms 13304 KB 
/**
 *    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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 344 KB Output isn't correct
11 Incorrect 47 ms 10084 KB Output isn't correct
12 Incorrect 36 ms 8880 KB Output isn't correct
13 Incorrect 33 ms 8524 KB Output isn't correct
14 Incorrect 49 ms 9108 KB Output isn't correct
15 Incorrect 60 ms 11256 KB Output isn't correct
16 Incorrect 85 ms 13304 KB Output isn't correct
17 Incorrect 60 ms 12660 KB Output isn't correct
18 Incorrect 63 ms 12644 KB Output isn't correct
19 Incorrect 56 ms 12644 KB Output isn't correct
20 Incorrect 58 ms 12524 KB Output isn't correct