oj.uz

Submission #866544

# Submission time Handle Problem Language Result Execution time Memory
866544 2023-10-26T10:47:00 Z nima_aryan Zoltan (COCI16_zoltan) C++17
14 / 140
 1000 ms 18136 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;
  }
}

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;
  }
  return a.max_lis > b.max_lis ? a : b;
}

struct SegmentTree {
  vector<Info> info;
  int n;

  SegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
  }

  void modify(int p, int l, int r, int x, Info v) {
    if (r - l == 1) {
      info[p] = info[p] + v;
      return;
    }
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void modify(int x, Info v) {
    modify(1, 0, n, x, v);
  }

  Info query(int p, int l, int r, int lx, int rx) {
    if (l >= rx || r <= lx) {
      return Info();
    }
    if (l >= lx && r <= rx) {
      return info[p];
    }
    int m = (l + r) / 2;
    return query(2 * p, l, m, lx, rx) +
           query(2 * p + 1, m, r, lx, rx);
  }
  Info query(int lx, int rx) {
    return query(1, 0, n, lx, rx);
  }
};

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();
  }
  SegmentTree seg(n + 1);
  seg.modify(n, Info{0, 1});
  vector<int> lis(n);
  vector<i64> cnt(n);
  for (int i = n - 1; i >= 0; --i) {
    Info best = seg.query(A[i] + 1, n + 1);
    lis[i] = best.max_lis + 1;
    cnt[i] = best.sum;
    seg.modify(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 pow2 = 1;
  while (32 - __builtin_ctz(pow2) - 1 < N - best) {
    pow2 = (pow2 * 2) % M;
  }
  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 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Execution timed out 1094 ms 348 KB Time limit exceeded
8 Execution timed out 1077 ms 600 KB Time limit exceeded
9 Execution timed out 1037 ms 344 KB Time limit exceeded
10 Execution timed out 1051 ms 348 KB Time limit exceeded
11 Execution timed out 1059 ms 15920 KB Time limit exceeded
12 Execution timed out 1077 ms 15060 KB Time limit exceeded
13 Execution timed out 1070 ms 10456 KB Time limit exceeded
14 Execution timed out 1078 ms 15040 KB Time limit exceeded
15 Execution timed out 1058 ms 16524 KB Time limit exceeded
16 Execution timed out 1043 ms 17956 KB Time limit exceeded
17 Execution timed out 1035 ms 18052 KB Time limit exceeded
18 Execution timed out 1051 ms 18136 KB Time limit exceeded
19 Execution timed out 1045 ms 17892 KB Time limit exceeded
20 Execution timed out 1042 ms 17916 KB Time limit exceeded