#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define left left123
#define right right123
const int MAXN = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
int a[MAXN];
pll t[MAXN * 4];
pll dpup[MAXN];
pll dpdown[MAXN];
ll pw[MAXN];
pll merge(const pll &a, const pll &b) {
if (a.f == b.f) return {a.f, (a.s + b.s) % mod};
return max(a, b);
}
void build(int v, int tl, int tr) {
t[v] = {0, 0};
if (tr - tl == 1) return;
int tm = tl + (tr - tl) / 2;
build(v * 2 + 1, tl, tm);
build(v * 2 + 2, tm, tr);
// for (int i = tl; i < tr; ++i) {
// t[i] = {0, 0};
// }
}
void upd(int v, int tl, int tr, int p, pll x) {
if (tr - tl == 1) {
t[v] = merge(t[v], x);
return;
}
int tm = tl + (tr - tl) / 2;
if (p < tm) {
upd(v * 2 + 1, tl, tm, p, x);
} else {
upd(v * 2 + 2, tm, tr, p, x);
}
t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
// t[p] = merge(t[p], x);
}
pll get(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return {0, 0};
if (l <= tl && tr <= r) return t[v];
int tm = tl + (tr - tl) / 2;
return merge(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm, tr, l, r));
// pll best = {0, 0};
// for (int i = l; i < r; ++i) {
// best = merge(best, t[i]);
// }
// return best;
}
void compress() {
vector<int> x;
rep(i, n) {
x.push_back(a[i]);
}
sort(all(x));
x.resize(unique(all(x)) - x.begin());
rep(i, n) {
a[i] = lower_bound(all(x), a[i]) - x.begin();
}
}
int main() {
pw[0] = 1;
for (int i = 1; i < MAXN; ++i) {
pw[i] = (pw[i - 1] * 2) % mod;
}
FAST_IO;
cin >> n;
rep(i, n) {
cin >> a[i];
}
compress();
for (int i = n - 1; i >= 0; --i) {
dpup[i] = max(make_pair(0LL, 1LL), get(0, 0, n, a[i] + 1, n));
dpup[i].f++;
upd(0, 0, n, a[i], dpup[i]);
}
build(0, 0, n);
for (int i = n - 1; i >= 0; --i) {
// cout << i << " : " << get(0, 0, n, 0, a[i]).f << endl;
dpdown[i] = max(make_pair(0LL, 1LL), get(0, 0, n, 0, a[i]));
dpdown[i].f++;
upd(0, 0, n, a[i], dpdown[i]);
}
// rep(i, n) {
// cout << "(" << dpup[i].f << ' ' << dpup[i].s << ") ";
// }
// cout << endl;
// rep(i, n) {
// cout << "(" << dpdown[i].f << ' ' << dpdown[i].s << ") ";
// }
// cout << endl;
pll ans = {0, 1};
rep(i, n) {
pll nw = {dpup[i].f, (dpup[i].s * pw[n - dpup[i].f - (i != 0)]) % mod};
ans = merge(ans, nw);
if (i == 0) continue;
nw = {dpdown[i].f, (dpdown[i].s * pw[n - dpdown[i].f - (i != 0)]) % mod};
ans = merge(ans, nw);
}
// if (ans.f == 1) {
// ans = {1, n};
// }i
build(0, 0, n + 1);
for (int i = 1; i < n; ++i) {
upd(0, 0, n + 1, a[i], dpdown[i]);
}
rep(i, n) {
pll nw = get(0, 0, n + 1, 0, a[i]);
nw.f += dpup[i].f;
nw.s *= dpup[i].s;
nw.s %= mod;
if (i == 0) {
nw.s *= pw[n - nw.f];
} else {
nw.s *= pw[n - 1 - nw.f];
}
nw.s %= mod;
ans = merge(ans, nw);
}
// for (int i = n - 1; i >= 0; --i) {
// // if (dpup[i].f == 1) continue;
// for (int j = 1; j < n; ++j) {
// if (i == j) continue;
// if (a[j] >= a[i]) continue;
// pll nw = {dpup[i].f + dpdown[j].f, (dpup[i].s * dpdown[j].s) % mod};
// // cout << nw.f << ' ' << nw.s << endl;
// if (i == 0) {
// nw.s *= pw[n - nw.f];
// } else {
// nw.s *= pw[n - 1 - nw.f];
// }
// nw.s %= mod;
// ans = merge(ans, nw);
// }
// }
if (ans.f == 1) {
ans = {1, pw[n - 1] * n};
ans.s %= mod;
}
cout << ans.f << ' ' << ans.s << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1888 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2040 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2040 KB |
Output is correct |
| 9 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2040 KB |
Output is correct |
| 11 |
Correct |
324 ms |
17080 KB |
Output is correct |
| 12 |
Correct |
291 ms |
16264 KB |
Output is correct |
| 13 |
Correct |
251 ms |
11724 KB |
Output is correct |
| 14 |
Correct |
345 ms |
16472 KB |
Output is correct |
| 15 |
Correct |
478 ms |
18204 KB |
Output is correct |
| 16 |
Correct |
543 ms |
19232 KB |
Output is correct |
| 17 |
Correct |
422 ms |
18500 KB |
Output is correct |
| 18 |
Correct |
437 ms |
18640 KB |
Output is correct |
| 19 |
Correct |
418 ms |
18692 KB |
Output is correct |
| 20 |
Correct |
432 ms |
18640 KB |
Output is correct |
