#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 1000003;
const int maxn = 2e5 + 5;
ll exp(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return ans;
}
struct SegTree {
int n;
vector<pii> tree;
SegTree(int _n) {
n = _n;
tree.resize(4*n+5);
}
pii merge(pii a, pii b) {
if(a.first > b.first) return a;
if(a.first < b.first) return b;
return { a.first, (a.second + b.second) % mod };
}
void update(int u, int tl, int tr, int p, int v, int w) {
if(tl == tr) {
tree[u] = merge(tree[u], { v, w });
} else {
int tm = (tl + tr) / 2;
if(p <= tm)
update(2*u, tl, tm, p, v, w);
else
update(2*u+1, tm+1, tr, p, v, w);
tree[u] = merge(tree[2*u], tree[2*u+1]);
}
}
pii query(int u, int tl, int tr, int l, int r) {
if(tl > tr || l > tr || tl > r) return { 0, 0 };
if(l <= tl && tr <= r) return tree[u];
int tm = (tl + tr) / 2;
return merge(
query(2*u, tl, tm, l, r),
query(2*u+1, tm+1, tr, l, r)
);
}
void update(int p, ll v, ll w) { update(1, 0, n-1, p, v, w); }
pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};
int32_t main() {
int n;
cin >> n;
vector<pii> lis(n), lds(n), v(n);
for(int i=0; i<n; i++) cin >> v[i].first, v[i].second = i;
sort(all(v), [&](pii &a, pii &b) {
if(a.first == b.first) return a.second < b.second;
return a.first > b.first;
});
set<int> s; s.insert(0);
for(auto &x : v) s.insert(x.first);
vector<int> comp(all(s));
SegTree dpL(n+1), dpR(n+1);
dpL.update(n, 0, 1); dpR.update(n, 0, 1);
for(auto [val, i] : v) {
auto [a, b] = dpL.query(i+1, n);
lis[i] = { a + 1, b };
dpL.update(i, a + 1, b);
}
sort(all(v), [&](pii &a, pii &b) {
if(a.first == b.first) return a.second < b.second;
return a.first < b.first;
});
for(auto [val, i] : v) {
auto [a, b] = dpR.query(i+1, n);
lds[i] = { a + 1, b };
dpR.update(i, a + 1, b);
}
ll len=0, ways=0;
for(int i=0; i<n; i++) {
ll L = lis[i].first + lds[i].first - 1;
ll W = (lis[i].second * lds[i].second) % mod;
if(L > len) len = L, ways = W;
else if(L == len) ways = (ways + W) % mod;
}
cout << len << '\n' << ways * exp(2, n - len) % mod << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 11 |
Runtime error |
204 ms |
37416 KB |
Memory limit exceeded |
| 12 |
Incorrect |
154 ms |
32600 KB |
Output isn't correct |
| 13 |
Incorrect |
164 ms |
30692 KB |
Output isn't correct |
| 14 |
Runtime error |
198 ms |
33056 KB |
Memory limit exceeded |
| 15 |
Runtime error |
263 ms |
40784 KB |
Memory limit exceeded |
| 16 |
Runtime error |
288 ms |
47400 KB |
Memory limit exceeded |
| 17 |
Runtime error |
247 ms |
45116 KB |
Memory limit exceeded |
| 18 |
Runtime error |
266 ms |
45428 KB |
Memory limit exceeded |
| 19 |
Runtime error |
224 ms |
45392 KB |
Memory limit exceeded |
| 20 |
Runtime error |
217 ms |
45308 KB |
Memory limit exceeded |
