#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int MOD = 1e9 + 7;
struct Node {
int val, w;
};
Node operator + (Node a, Node b) {
if (a.val == b.val) {
Node c = { a.val, a.w + b.w };
if (c.w >= MOD)
c.w -= MOD;
return c;
}
if (a.val > b.val)
return a;
return b;
}
const int N = 2e5 + 5;
Node t[N * 4], mxr[N], mxl[N];
vector<int> vd;
int a[N];
void upd(int x, Node y, int v = 1, int L = 0, int R = vd.size() - 1) {
if (L == R) {
t[v] = y;
}
else {
int m = (L + R) >> 1;
if (x <= m)
upd(x, y, v * 2, L, m);
else
upd(x, y, v * 2 + 1, m + 1, R);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
Node que(int l, int r, int v = 1, int L = 0, int R = vd.size() - 1) {
if (l > r)
return { 0, 1 };
if (l == L && r == R) {
return t[v];
}
int m = (L + R) >> 1;
return que(l, min(m, r), v * 2, L, m) +
que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
vd.push_back(a[i]);
}
sort(all(vd));
vd.erase(unique(all(vd)), vd.end());
for (int i = 0; i < n; i++) {
a[i] = lower_bound(all(vd), a[i]) - vd.begin();
}
fill(t, t + N * 4, (Node){ 0, 1 });
for (int i = n - 1; i >= 0; i--) {
Node res = que(a[i] + 1, vd.size() - 1);
res.val++;
upd(a[i], res);
mxr[i] = res;
}
fill(t, t + N * 4, (Node){ 0, 1 });
for (int i = n - 1; i > 0; i--) {
Node res = que(0, a[i] - 1);
res.val++;
upd(a[i], res);
}
Node mx_subseq = { 0, 0 }, mx_subseq_with_first = { 0, 0 };
for (int i = 0; i < n; i++) {
Node cur = que(0, a[i] - 1);
cur.val += mxr[i].val;
cur.w = cur.w * (ll)mxr[i].w % MOD;
if (i == 0)
mx_subseq_with_first = mx_subseq_with_first + cur;
else
mx_subseq = mx_subseq + cur;
}
for (int i = 0; i < n - 1 - (mx_subseq.val > 1 ? mx_subseq.val : 0); i++) {
mx_subseq.w = mx_subseq.w * 2 % MOD;
}
for (int i = 0; i < n - mx_subseq_with_first.val; i++) {
mx_subseq_with_first.w = mx_subseq_with_first.w * 2 % MOD;
}
Node ans = mx_subseq + mx_subseq_with_first;
cout << ans.val << " " << ans.w;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6648 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
6656 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
6648 KB |
Output isn't correct |
| 4 |
Correct |
8 ms |
6648 KB |
Output is correct |
| 5 |
Correct |
9 ms |
6564 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6648 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
6648 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
6648 KB |
Output isn't correct |
| 9 |
Incorrect |
11 ms |
6648 KB |
Output isn't correct |
| 10 |
Incorrect |
9 ms |
6648 KB |
Output isn't correct |
| 11 |
Incorrect |
204 ms |
10480 KB |
Output isn't correct |
| 12 |
Incorrect |
184 ms |
10116 KB |
Output isn't correct |
| 13 |
Incorrect |
163 ms |
9716 KB |
Output isn't correct |
| 14 |
Incorrect |
235 ms |
10220 KB |
Output isn't correct |
| 15 |
Incorrect |
299 ms |
11128 KB |
Output isn't correct |
| 16 |
Incorrect |
349 ms |
11756 KB |
Output isn't correct |
| 17 |
Incorrect |
278 ms |
11116 KB |
Output isn't correct |
| 18 |
Incorrect |
274 ms |
11184 KB |
Output isn't correct |
| 19 |
Incorrect |
269 ms |
11116 KB |
Output isn't correct |
| 20 |
Incorrect |
271 ms |
11116 KB |
Output isn't correct |
