#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair <int, int>, null_type,less<pair <int, int>>, rb_tree_tag,tree_order_statistics_node_update>
const int MAXN = 2e5 + 10, MAXM = 1e2 + 10, MOD = 1000000000 + 7, MOD1 = 1e9 + 9, SQ = 350;
const long long INF = 1e9 + 11;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[MAXN], seg[4 * MAXN][2], dp[MAXN][2], cnt[MAXN][2], fen[MAXN][2], p2[MAXN];
vector <int> vec[MAXN][2];
void upd(int l, int r, int id, int ind, int val, int index) {
if (l == r) {
seg[id][index] = val;
return;
}
int mid = (l + r) / 2;
if (ind <= mid)
upd(l, mid, 2 * id, ind, val, index);
else
upd(mid + 1, r, 2 * id + 1, ind, val, index);
seg[id][index] = max(seg[2 * id][index], seg[2 * id + 1][index]);
}
int get(int l, int r, int id, int l1, int r1, int index) {
if (r < l1 || r1 < l)
return 0;
if (l1 <= l && r <= r1)
return seg[id][index];
int mid = (l + r) / 2;
return max(get(l, mid, 2 * id, l1, r1, index), get(mid + 1, r, 2 * id + 1, l1, r1, index));
}
void upd(int x, int val, int ind) {
x++;
for (; x < MAXN; x += x & (-x))
fen[x][ind] = (fen[x][ind] + val) % MOD;
}
int get(int x, int ind) {
int res = 0;
for (; x; x -= x & (-x))
res = (res + fen[x][ind]) % MOD;
return res;
}
int get(int l, int r, int ind) {
l++;
r++;
return ((get(r, ind) - get(l - 1, ind)) % MOD + MOD) % MOD;
}
void solve() {
int n;
cin >> n;
vector <int> kol;
p2[0] = 1;
for (int i = 0; i < n; i++) {
cin >> a[i];
p2[i + 1] = 1ll * p2[i] * 2 % MOD;
kol.push_back(a[i]);
}
sort(kol.begin(), kol.end());
kol.resize(unique(kol.begin(), kol.end()) - kol.begin());
for (int i = 0; i < n; i++)
a[i] = lower_bound(kol.begin(), kol.end(), a[i]) - kol.begin();
for (int i = n - 1; i >= 0; i--) {
dp[i][0] = get(0, n, 1, a[i] + 1, n, 0) + 1;
dp[i][1] = get(0, n, 1, 0, a[i] - 1, 1) + 1;
upd(0, n, 1, a[i], dp[i][0], 0);
upd(0, n, 1, a[i], dp[i][1], 1);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i][0] + dp[i][1] - 1);
vec[dp[i][0]][0].push_back(i);
vec[dp[i][1]][1].push_back(i);
if (dp[i][0] == 1)
cnt[i][0] = 1;
if (dp[i][1] == 1)
cnt[i][1] = 1;
}
for (int i = 1; i < ans; i++) {
int r = vec[i][0].size() - 1;
// cout << i << " =\n";
// for (int t = 0; t < n; t++)
// cout << get(t, t, 0) << " ";
// cout << "\n";
for (int j = vec[i + 1][0].size() - 1; j >= 0; j--) {
int ind = vec[i + 1][0][j];
while (r >= 0 && vec[i][0][r] > ind) {
int ind1 = vec[i][0][r];
upd(a[ind1], cnt[ind1][0], 0);
r--;
}
// cout << ind << " = ";
// for (int t = 0; t < n; t++)
// cout << get(t, t, 0) << " ";
// cout << "\n";
cnt[ind][0] = get(a[ind] + 1, n, 0);
}
int r1 = vec[i][1].size() - 1;
for (int j = vec[i + 1][1].size() - 1; j >= 0; j--) {
int ind = vec[i + 1][1][j];
while (r1 >= 0 && vec[i][1][r1] > ind) {
int ind1 = vec[i][1][r1];
upd(a[ind1], cnt[ind1][1], 1);
r1--;
}
cnt[ind][1] = get(0, a[ind] - 1, 1);
}
for (int j = r + 1; j < vec[i][0].size(); j++) {
int ind = vec[i][0][j];
upd(a[ind], -cnt[ind][0], 0);
}
for (int j = r1 + 1; j < vec[i][1].size(); j++) {
int ind = vec[i][1][j];
upd(a[ind], -cnt[ind][1], 1);
}
}
int ans1 = 0;
for (int i = 0; i < n; i++) {
if (dp[i][0] + dp[i][1] - 1 == ans) {
// cout << i << " " << cnt[i][0] << " " << cnt[i][1] << "\n";
int tmp = 1ll * cnt[i][0] * cnt[i][1] % MOD;
tmp = 1ll * tmp * p2[n - ans] % MOD;
ans1 = (ans1 + tmp) % MOD;
}
}
cout << ans << " " << ans1 << "\n";
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
// cin >> q;
while (q--) {
solve();
}
}
Compilation message
zoltan.cpp: In function 'void solve()':
zoltan.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int j = r + 1; j < vec[i][0].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
zoltan.cpp:133:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int j = r1 + 1; j < vec[i][1].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 6 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 7 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 8 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 9 |
Correct |
4 ms |
14940 KB |
Output is correct |
| 10 |
Correct |
3 ms |
14940 KB |
Output is correct |
| 11 |
Correct |
142 ms |
24056 KB |
Output is correct |
| 12 |
Correct |
128 ms |
23612 KB |
Output is correct |
| 13 |
Correct |
115 ms |
21204 KB |
Output is correct |
| 14 |
Correct |
158 ms |
21844 KB |
Output is correct |
| 15 |
Correct |
186 ms |
22984 KB |
Output is correct |
| 16 |
Correct |
217 ms |
23752 KB |
Output is correct |
| 17 |
Correct |
199 ms |
26036 KB |
Output is correct |
| 18 |
Correct |
194 ms |
26172 KB |
Output is correct |
| 19 |
Correct |
194 ms |
26116 KB |
Output is correct |
| 20 |
Correct |
204 ms |
26060 KB |
Output is correct |
