#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 = 1e6 + 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++) {
for (int ind: vec[i][0])
upd(a[ind], cnt[ind][0], 0);
for (int ind: vec[i][1])
upd(a[ind], cnt[ind][1], 1);
// cout << i << " = ";
// for (int i = 0; i < n; i++)
// cout << get(i, i, 0) << " ";
// cout << "\n";
for (int ind: vec[i + 1][0])
cnt[ind][0] = get(a[ind] + 1, n, 0);
for (int ind: vec[i + 1][1])
cnt[ind][1] = get(0, a[ind] - 1, 1);
for (int ind: vec[i][0])
upd(a[ind], -cnt[ind][0], 0);
for (int ind: vec[i][1])
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) {
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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
53852 KB |
Memory limit exceeded |
| 2 |
Runtime error |
11 ms |
53912 KB |
Memory limit exceeded |
| 3 |
Runtime error |
11 ms |
53852 KB |
Memory limit exceeded |
| 4 |
Runtime error |
11 ms |
53852 KB |
Memory limit exceeded |
| 5 |
Runtime error |
11 ms |
53852 KB |
Memory limit exceeded |
| 6 |
Runtime error |
10 ms |
53852 KB |
Memory limit exceeded |
| 7 |
Runtime error |
14 ms |
53940 KB |
Memory limit exceeded |
| 8 |
Runtime error |
13 ms |
53852 KB |
Memory limit exceeded |
| 9 |
Runtime error |
13 ms |
53848 KB |
Memory limit exceeded |
| 10 |
Runtime error |
11 ms |
54104 KB |
Memory limit exceeded |
| 11 |
Runtime error |
128 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
136 ms |
65012 KB |
Memory limit exceeded |
| 13 |
Runtime error |
129 ms |
64804 KB |
Memory limit exceeded |
| 14 |
Runtime error |
160 ms |
65488 KB |
Memory limit exceeded |
| 15 |
Runtime error |
156 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
191 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
154 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
158 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 9 |
