#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7, MOD = 1000 * 1000 * 1000 + 7;
int a[N], l[N], r[N], cntl[N], cntr[N], pw[N];
struct Seg {
ii tree[N << 2];
ii merge(ii a, ii b) {
if (a.f > b.f)
return a;
if (b.f > a.f)
return b;
return mp(a.f, (a.s + b.s) % MOD);
}
void add(int v, int l, int r, int i, ii e) {
if (l == r) {
tree[v] = merge(tree[v], e);
return;
}
int m = (l + r) >> 1;
if (i <= m)
add(v * 2 + 1, l, m, i, e);
else
add(v * 2 + 2, m + 1, r, i, e);
tree[v] = merge(tree[v * 2 + 1], tree[v * 2 + 2]);
}
ii get(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl)
return mp(0, 0);
if (l <= tl && tr <= r)
return tree[v];
int m = (tl + tr) >> 1;
return merge(get(v * 2 + 1, tl, m, l, r), get(v * 2 + 2, m + 1, tr, l, r));
}
} L, R;
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
pw[0] = 1;
for (int i = 1; i < N; ++i)
pw[i] = (pw[i - 1] * 2) % MOD;
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector <int> c;
for (int i = 0; i < n; ++i)
c.app(a[i]);
sort(all(c));
c.resize(unique(all(c)) - c.begin());
for (int i = 0; i < n; ++i)
a[i] = lower_bound(all(c), a[i]) - c.begin();
int len = 0;
for (int i = n; i; --i) {
tie(l[i], cntl[i]) = L.get(0, 0, N, 0, a[i] - 1);
++l[i];
if (l[i] == 1)
cntl[i] = 1;
tie(r[i], cntr[i]) = R.get(0, 0, N, a[i] + 1, N);
++r[i];
if (r[i] == 1)
cntr[i] = 1;
L.add(0, 0, N, a[i], mp(l[i], cntl[i]));
R.add(0, 0, N, a[i], mp(r[i], cntr[i]));
len = max(len, l[i] + r[i] - 1);
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (l[i] + r[i] - 1 == len) {
ans += (cntl[i] * cntr[i]) % MOD;
ans %= MOD;
}
}
ans = ans * pw[n - len] % MOD;
cout << len << ' ' << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2048 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
2048 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
2048 KB |
Output isn't correct |
| 4 |
Correct |
6 ms |
2048 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2048 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 7 |
Incorrect |
7 ms |
2304 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
2304 KB |
Output isn't correct |
| 9 |
Incorrect |
7 ms |
2304 KB |
Output isn't correct |
| 10 |
Incorrect |
7 ms |
2176 KB |
Output isn't correct |
| 11 |
Incorrect |
186 ms |
23784 KB |
Output isn't correct |
| 12 |
Incorrect |
150 ms |
20840 KB |
Output isn't correct |
| 13 |
Incorrect |
149 ms |
19824 KB |
Output isn't correct |
| 14 |
Incorrect |
221 ms |
21348 KB |
Output isn't correct |
| 15 |
Incorrect |
283 ms |
26088 KB |
Output isn't correct |
| 16 |
Incorrect |
342 ms |
29676 KB |
Output isn't correct |
| 17 |
Incorrect |
217 ms |
26476 KB |
Output isn't correct |
| 18 |
Incorrect |
229 ms |
26472 KB |
Output isn't correct |
| 19 |
Incorrect |
217 ms |
26600 KB |
Output isn't correct |
| 20 |
Incorrect |
225 ms |
26600 KB |
Output isn't correct |
