#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5, M=1e9+7;
int n, a[mxN];
ar<int, 2> ic[mxN], dc[mxN], st[1<<19];
vector<int> d;
ar<int, 2> inc(ar<int, 2> x) {
++x[0];
return x;
}
ar<int, 2> cmb(ar<int, 2> x, ar<int, 2> y) {
return x[0]^y[0]?max(x, y):ar<int, 2>{x[0], (x[1]+y[1])%M};
}
void upd(int i, ar<int, 2> x, int u=1, int l=0, int r=d.size()-1) {
if (l==r) {
st[u]=cmb(st[u], x);
return;
}
int mid=(l+r)/2;
i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
st[u]=cmb(st[2*u], st[2*u+1]);
}
ar<int, 2> qry(int ql, int qr, int u=1, int l=0, int r=d.size()-1) {
if (l>qr||r<ql)
return {0, 0};
if (ql<=l&&r<=qr)
return st[u];
int mid=(l+r)/2;
return cmb(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}
void psh(ar<int, 2> t[], int u=1, int l=0, int r=d.size()-1) {
if (l==r) {
t[l]=st[u];
st[u]={};
return;
}
st[u]={};
int mid=(l+r)/2;
psh(t, 2*u, l, mid);
psh(t, 2*u+1, mid+1, r);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=0; i<n; ++i)
cin >> a[i];
d=vector<int>(a, a+n);
sort(d.begin(), d.end());
d.resize(unique(d.begin(), d.end())-d.begin());
for (int i=n-1; ~i; --i) {
a[i]=lower_bound(d.begin(), d.end(), a[i])-d.begin();
upd(a[i], cmb(inc(qry(a[i]+1, d.size()-1)), {1, 1}));
}
psh(ic);
for (int i=n-1; ~i; --i)
upd(a[i], cmb(inc(qry(0, a[i]-1)), {1, 1}));
psh(dc);
for (int i=(int)d.size()-2; ~i; --i)
ic[i]=cmb(ic[i], ic[i+1]);
int l=ic[0][0];
for (int i=0; i<d.size(); ++i) {
l=max(l, dc[i][0]);
if (i+1<d.size())
l=max(l, dc[i][0]+ic[i+1][0]);
}
ll ans=ic[0][0]==l?ic[0][1]:0;
for (int i=0; i<d.size(); ++i) {
if (dc[i][0]==l)
ans=(ans+dc[i][1])%M;
if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
ans=(ans+(ll)dc[i][1]*ic[i+1][1])%M;
}
for (int i=0; i<n-l; ++i)
ans=ans*2%M;
ans=ans*(M+1)/2%M;
cout << l << " " << ans;
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i=0; i<d.size(); ++i) {
| ~^~~~~~~~~
zoltan.cpp:74:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (i+1<d.size())
| ~~~^~~~~~~~~
zoltan.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i=0; i<d.size(); ++i) {
| ~^~~~~~~~~
zoltan.cpp:81:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
| ~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
193 ms |
9224 KB |
Output is correct |
| 12 |
Correct |
172 ms |
8664 KB |
Output is correct |
| 13 |
Correct |
159 ms |
6460 KB |
Output is correct |
| 14 |
Correct |
242 ms |
8884 KB |
Output is correct |
| 15 |
Correct |
265 ms |
10052 KB |
Output is correct |
| 16 |
Correct |
356 ms |
10956 KB |
Output is correct |
| 17 |
Correct |
246 ms |
9836 KB |
Output is correct |
| 18 |
Correct |
254 ms |
9812 KB |
Output is correct |
| 19 |
Correct |
249 ms |
9808 KB |
Output is correct |
| 20 |
Correct |
246 ms |
9844 KB |
Output is correct |
