/**
* 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;
}
Compilation message
zoltan.cpp: In function 'auto LIS(const std::vector<int>&)':
zoltan.cpp:75:14: error: missing template arguments before '(' token
75 | return pair(lis, cnt);
| ^
zoltan.cpp: In function 'int main()':
zoltan.cpp:87:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | auto [lis, cnt_lis] = LIS(A);
| ^
zoltan.cpp:91:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | auto [lds, cnt_lds] = LIS(A);
| ^
