제출 #866522

#제출 시각아이디문제언어결과실행 시간메모리
866522nima_aryanZoltan (COCI16_zoltan)C++17
14 / 140
85 ms13304 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; } } template <typename T> class Fenwick { public: vector<T> fenw; int n; Fenwick(int n) : n(n) { fenw.resize(n); } void modify(int x, T v) { for (int i = x + 1; i <= n; i += i & -i) { fenw[i - 1] = fenw[i - 1] + v; } } T query(int x) { T res{}; for (int i = x; i > 0; i -= i & -i) { res = res + fenw[i - 1]; } return res; } }; struct Item { int best; }; Item operator+(Item a, Item b) { if (b.best > a.best) { swap(a, b); } return a; } auto LIS(const vector<int>& A) { int n = A.size(); vector<int> p(n); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](int i, int j) { return A[i] > A[j]; }); vector<int> lis(n); vector<i64> cnt(n); Fenwick<Item> fen(n); // i -> n-i-1 (suffix fenwick) vector<i64> sum(n + 1); sum[0] = 1; for (int i : p) { lis[i] = fen.query(n - i).best; cnt[i] = sum[lis[i]]; lis[i] += 1; fen.modify(n - i - 1, Item{lis[i]}); add(sum[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; }
#Verdict Execution timeMemoryGrader output
Fetching results...