oj.uz

Submission #866545

# Submission time Handle Problem Language Result Execution time Memory
866545 2023-10-26T10:49:00 Z nima_aryan Zoltan (COCI16_zoltan) C++17
42 / 140
 1000 ms 17960 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 (64 - __builtin_clzll(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
42.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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1065 ms 348 KB Time limit exceeded
8 Execution timed out 1039 ms 344 KB Time limit exceeded
9 Execution timed out 1072 ms 348 KB Time limit exceeded
10 Execution timed out 1078 ms 348 KB Time limit exceeded
11 Execution timed out 1077 ms 16024 KB Time limit exceeded
12 Execution timed out 1067 ms 15064 KB Time limit exceeded
13 Execution timed out 1070 ms 10448 KB Time limit exceeded
14 Execution timed out 1049 ms 15056 KB Time limit exceeded
15 Execution timed out 1043 ms 16492 KB Time limit exceeded
16 Execution timed out 1070 ms 17960 KB Time limit exceeded
17 Execution timed out 1052 ms 17824 KB Time limit exceeded
18 Execution timed out 1010 ms 17832 KB Time limit exceeded
19 Execution timed out 1059 ms 17916 KB Time limit exceeded
20 Execution timed out 1074 ms 17916 KB Time limit exceeded