Submission #866544

#TimeUsernameProblemLanguageResultExecution timeMemory
866544nima_aryanZoltan (COCI16_zoltan)C++17
14 / 140
1094 ms18136 KiB
/** * 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...