#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+9;
const ll LOGN = 20;
const ll MAXN = 2e5 + 100;
#define int long long
vector<pair<int,int>> v;
vector<int> arr, cc;
pair<int,int> sg[4*MAXN], w1[MAXN], w2[MAXN];
pair<int,int> merge(pair<int,int> a, pair<int,int> b) {
if (a.f == b.f)
return {a.f, (a.s + b.s) % MOD};
return max(a, b);
}
void update(int k, int a, int b, int plc, pair<int,int> val) {
if (b < plc || a > plc)
return ;
if (a == b) {
sg[k] = merge(val, sg[k]);
return ;
}
update(2*k, a, (a+b)/2, plc, val);
update(2*k+1, (a+b)/2+1, b, plc, val);
sg[k] = merge(sg[2*k], sg[2*k+1]);
}
pair<int,int> query(int k, int a, int b, int q_l, int q_r) {
if (b < q_l || a > q_r)
return {0, 0};
if (q_l <= a && b <= q_r)
return sg[k];
return merge(query(2*k, a, (a+b)/2, q_l, q_r),
query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}
int index(int k) {
return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}
map<int,int> cnt;
signed main() {
fast
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
cc.push_back(A[i]);
cnt[A[i]]++;
}
for (int i = 0; i < N; i++)
v.push_back({A[i], i+1});
sort(v.begin(), v.end(), [&](pair<int,int> a, pair<int,int> b) {
return make_pair(a.f, -a.s) < make_pair(b.f, -b.s);
});
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (auto u : v)
arr.push_back(u.s);
for (int i = 0; i < N; i++) {
pair<int,int> Q = query(1, 0, N, index(arr[i]) + 1, N);
if (Q.f == 0)
Q.s++;
w1[i+1] = {Q.f + 1, Q.s};
update(1, 0, N, index(arr[i]), w1[i+1]);
}
for (int i = 0; i < 4*MAXN; i++)
sg[i] = {0, 0};
for (int i = N-1; i >= 0; i--) {
pair<int,int> Q = query(1, 0, N, index(arr[i]) + 1, N);
if (Q.f == 0)
Q.s++;
w2[i+1] = {Q.f + 1, Q.s};
update(1, 0, N, index(arr[i]), w2[i+1]);
}
pair<int,int> ans = {0, 0};
for (int i = 1; i <= N; i++)
ans = merge(ans, {w1[i].f + w2[i].f - 1, (w1[i].s * w2[i].s) % MOD});
for (auto u : cnt)
ans.s = (ans.s * u.s) % MOD;
cout << ans.f << " " << ans.s << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 5 |
Correct |
2 ms |
14940 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
14940 KB |
Output isn't correct |
| 11 |
Runtime error |
173 ms |
38388 KB |
Memory limit exceeded |
| 12 |
Runtime error |
153 ms |
35132 KB |
Memory limit exceeded |
| 13 |
Incorrect |
137 ms |
32092 KB |
Output isn't correct |
| 14 |
Runtime error |
162 ms |
35680 KB |
Memory limit exceeded |
| 15 |
Runtime error |
209 ms |
38368 KB |
Memory limit exceeded |
| 16 |
Runtime error |
242 ms |
41244 KB |
Memory limit exceeded |
| 17 |
Runtime error |
264 ms |
39736 KB |
Memory limit exceeded |
| 18 |
Runtime error |
271 ms |
40476 KB |
Memory limit exceeded |
| 19 |
Runtime error |
260 ms |
39452 KB |
Memory limit exceeded |
| 20 |
Runtime error |
273 ms |
39700 KB |
Memory limit exceeded |
