oj.uz

Submission #866546

# Submission time Handle Problem Language Result Execution time Memory
866546 2023-10-26T10:50:26 Z nima_aryan Zoltan (COCI16_zoltan) C++17
140 / 140
 223 ms 18012 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 rem = N - best;
  while (rem > 0) {
    pow2 = (pow2 * 2) % M;
    rem -= 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 424 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 348 KB Output is correct
11 Correct 123 ms 15924 KB Output is correct
12 Correct 118 ms 15020 KB Output is correct
13 Correct 93 ms 10388 KB Output is correct
14 Correct 144 ms 15080 KB Output is correct
15 Correct 180 ms 16492 KB Output is correct
16 Correct 223 ms 17956 KB Output is correct
17 Correct 153 ms 17976 KB Output is correct
18 Correct 151 ms 17916 KB Output is correct
19 Correct 160 ms 18012 KB Output is correct
20 Correct 158 ms 17912 KB Output is correct