#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 100;
vector<ll> A, cc;
int sg[4*MAXN];
int index(int k) {
return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}
void update(int k, int a, int b, int plc, int val) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k] = max(sg[k], val);
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = max(sg[2*k], sg[2*k+1]);
}
int query(int k, int a, int b, int q_l, int q_r) {
if (b < q_l || a > q_r)
return 0;
if (q_l <= a && b <= q_r)
return sg[k];
return max(query(2*k, a, (a+b)/2, q_l, q_r),
query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}
pair<int,ll> merge(pair<int,ll> a, pair<int,ll> b) {
if (a.f == b.f)
return {a.f, (a.s + b.s) % MOD};
return max(a, b);
}
ll expo(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)
res = (res * a) % MOD;
a = (a * a) % MOD;
b /= 2;
}
return res;
}
int LIS[MAXN], LDS[MAXN];
int main() {
fast
int N;
cin >> N;
A = vector<ll>(N+1);
for (int i = 1; i <= N; i++) {
cin >> A[i];
cc.push_back(A[i]);
}
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (int i = N; i >= 1; i--) {
int Q = query(1, 0, N, index(A[i]) + 1, N);
LIS[i] = Q + 1;
update(1, 0, N, index(A[i]), LIS[i]);
}
for (int i = 0; i < 4*MAXN; i++)
sg[i] = 0;
for (int i = N; i >= 1; i--) {
int Q = query(1, 0, N, 0, index(A[i]) - 1);
LDS[i] = Q + 1;
update(1, 0, N, index(A[i]), LDS[i]);
}
pair<int,ll> ans = {0, 0};
for (int i = 1; i <= N; i++)
ans = merge(ans, {LDS[i] + LIS[i] - 1, expo(2, N - LDS[i] - LIS[i] + 1)});
cout << ans.f << " " << ans.s << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
3416 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
3420 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 6 |
Correct |
1 ms |
3420 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 11 |
Incorrect |
165 ms |
8568 KB |
Output isn't correct |
| 12 |
Incorrect |
140 ms |
7924 KB |
Output isn't correct |
| 13 |
Incorrect |
131 ms |
7628 KB |
Output isn't correct |
| 14 |
Incorrect |
180 ms |
8460 KB |
Output isn't correct |
| 15 |
Incorrect |
221 ms |
9164 KB |
Output isn't correct |
| 16 |
Incorrect |
255 ms |
9932 KB |
Output isn't correct |
| 17 |
Incorrect |
208 ms |
9436 KB |
Output isn't correct |
| 18 |
Incorrect |
198 ms |
9488 KB |
Output isn't correct |
| 19 |
Incorrect |
201 ms |
9636 KB |
Output isn't correct |
| 20 |
Incorrect |
200 ms |
9792 KB |
Output isn't correct |
