oj.uz

Submission #866543

# Submission time Handle Problem Language Result Execution time Memory
866543 2023-10-26T10:45:42 Z nima_aryan Zoltan (COCI16_zoltan) C++17
140 / 140
 212 ms 18016 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;
  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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 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 600 KB Output is correct
11 Correct 128 ms 16020 KB Output is correct
12 Correct 108 ms 15056 KB Output is correct
13 Correct 97 ms 10400 KB Output is correct
14 Correct 134 ms 15080 KB Output is correct
15 Correct 174 ms 16680 KB Output is correct
16 Correct 212 ms 17828 KB Output is correct
17 Correct 162 ms 17840 KB Output is correct
18 Correct 160 ms 18016 KB Output is correct
19 Correct 150 ms 17888 KB Output is correct
20 Correct 154 ms 17916 KB Output is correct