#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define lowbit(x) x&-x
const int N=2e5+10,mod=1e9+7;
int n,A[N];
LL ans1,ans2,dp1[N],dp2[N],cnt1[N],cnt2[N],fac[N];
vector<int> vec;
struct node
{
int val;
LL num;
node() {val=0,num=1;}
inline void add(int x,LL y)
{
if(x>val) val=x,num=y;
else if(x==val) num=(num+y)%mod;
}
}C1[N],C2[N];
inline void insert(int x,int y,LL z,node C[])
{
for(;x<=n+1;x+=lowbit(x)) C[x].add(y,z);
}
inline node query(int x,node C[])
{
node res;
for(;x;x-=lowbit(x)) res.add(C[x].val,C[x].num);
res.num=res.val?res.num:1;
return res;
}
int main()
{
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*2%mod;
for(int i=1;i<=n;i++) scanf("%d",&A[i]),vec.push_back(A[i]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int i=1;i<=n;i++) A[i]=lower_bound(vec.begin(),vec.end(),A[i])-vec.begin()+2;
for(int i=n;i>=1;i--)
{
node up=query(n+1-A[i],C1),down=query(A[i]-1,C2);
dp1[i]=up.val+1,cnt1[i]=up.num;;
dp2[i]=down.val+1,cnt2[i]=down.num;
insert(n+2-A[i],dp1[i],cnt1[i],C1);
insert(A[i],dp2[i],cnt2[i],C2);
}
for(int i=1;i<=n;i++)
{
int len=dp1[i]+dp2[i]-1;
if(len>ans1) ans1=len,ans2=cnt1[i]*cnt2[i]%mod*fac[n-len]%mod;
else if(len==ans1) ans2=(ans2+cnt1[i]*cnt2[i]%mod*fac[n-len]%mod)%mod;
}
printf("%lld %lld",ans1,ans2);
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
zoltan.cpp:36:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | for(int i=1;i<=n;i++) scanf("%d",&A[i]),vec.push_back(A[i]);
| ~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14936 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14976 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14936 KB |
Output is correct |
11 |
Correct |
54 ms |
17116 KB |
Output is correct |
12 |
Correct |
45 ms |
16584 KB |
Output is correct |
13 |
Correct |
41 ms |
16400 KB |
Output is correct |
14 |
Correct |
64 ms |
16840 KB |
Output is correct |
15 |
Correct |
79 ms |
17632 KB |
Output is correct |
16 |
Correct |
104 ms |
17856 KB |
Output is correct |
17 |
Correct |
66 ms |
17212 KB |
Output is correct |
18 |
Correct |
64 ms |
17344 KB |
Output is correct |
19 |
Correct |
63 ms |
17348 KB |
Output is correct |
20 |
Correct |
70 ms |
17348 KB |
Output is correct |