//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int long long
using namespace std;
const int N = 200005,mx = 200005,mod=1000000007;
int a[N];
pair <int,int> inc[N],t[4*N],dc[N];
vector <pair<int,int>> d;
void upd(int h,int l,int r,int idx,int val1,int val2){
if (l == r){
if(val1>t[h].f)
t[h] = {val1,val2};
else if(val1==t[h].f)
t[h].s=(t[h].s + val2)%mod;
return;
}
if (idx > (l+r)>>1) upd(right,idx,val1,val2);
else upd(left,idx,val1,val2);
if (t[h*2].f == t[h*2 + 1].f) t[h] = {t[h*2].f,(t[h*2+1].s + t[h*2].s)%mod};
else if(t[h*2].f > t[h*2 + 1].f) t[h] = t[h*2];
else t[h] = t[h*2 + 1];
}
pair<int,int> get(int h,int l,int r,int L,int R){
if (r < L || R < l) return {0,0};
if (L <= l && r <= R) return t[h];
pair <int,int> x = get(left,L,R),y = get(right,L,R);
if (x.f == y.f) return {x.f,(x.s+y.s)%mod};
else if(x.f > y.f) return x;
return y;
}
void build(int h,int l,int r){
if (l==r){
t[h] = {0,0};
return;
}
build(left),build(right);
t[h] = {0,0};
}
int pwr(int a,int b){
int res=1;
while(b){
if (b%2) res=(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for(int i =1; i<=n;i++){
cin>>a[i];
d.pb({a[i],i});
}
sort(d.begin(),d.end());
a[d[0].s] = 1;
for (int i=1;i<d.size();i++){
a[d[i].s] = a[d[i - 1].s];
if (d[i].f > d[i - 1].f) a[d[i].s]++;
}
//increasing
for (int i = n; i >= 1; i--){
pair <int,int> g = get(1,1,mx,a[i] + 1,mx);
inc[i] = {g.f + 1,g.s};
if (g.f > 0){
upd(1,1,mx,a[i],g.f+1,g.s);
}else{
inc[i].s = 1;
upd(1,1,mx,a[i],1,1);
}
}
build(1,1,mx);
//decreasing
for (int i = n; i >= 1; i--){
pair <int,int> g = get(1,1,mx,1,a[i] - 1);
dc[i] = {g.f + 1,g.s};
if (g.f > 0){
upd(1,1,mx,a[i],g.f+1,g.s);
}else{
dc[i].s = 1;
upd(1,1,mx,a[i],1,1);
}
}
int mxlen = 0,ans = 0;
for (int i = 1; i <= n; i++){
int cur = inc[i].f + dc[i].f - 1;
if (mxlen == cur){
ans = (ans + (inc[i].s*dc[i].s)%mod)%mod;
}else if (mxlen < cur){
mxlen = cur;
ans = (inc[i].s*dc[i].s)%mod;
}
}
ans = (ans*pwr(2,n - mxlen))%mod;
cout<<mxlen<<" "<<ans;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=1;i<d.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8532 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8532 KB |
Output is correct |
| 6 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 7 |
Correct |
6 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
6 ms |
8532 KB |
Output is correct |
| 9 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 10 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 11 |
Correct |
117 ms |
17268 KB |
Output is correct |
| 12 |
Correct |
105 ms |
16172 KB |
Output is correct |
| 13 |
Correct |
98 ms |
15692 KB |
Output is correct |
| 14 |
Correct |
198 ms |
16208 KB |
Output is correct |
| 15 |
Correct |
169 ms |
17964 KB |
Output is correct |
| 16 |
Correct |
228 ms |
19496 KB |
Output is correct |
| 17 |
Correct |
200 ms |
19556 KB |
Output is correct |
| 18 |
Correct |
167 ms |
19504 KB |
Output is correct |
| 19 |
Correct |
157 ms |
19556 KB |
Output is correct |
| 20 |
Correct |
157 ms |
19616 KB |
Output is correct |
