#include<bits/stdc++.h>
using namespace std;
int ar[200005];
int md=1e9+7;
struct node{
int l;
long long w;
node(int a=0,int b=1){
l=a,w=b;
}
friend node operator+(node a,node b){
node c;
c.l=max(a.l,b.l);
c.w=a.l==b.l?a.w+b.w:a.l>b.l?a.w:b.w;
if(c.l==0)c.w=1;
c.w%=md;
return c;
}
};
struct segtree{
node info[800005];
void upd(int st,int en,int i,int pos,int len,int way){
if(st>pos||en<pos)return;
if(st==en)return void(info[i]=info[i]+node(len,way));
int m=(st+en)/2;
upd(st,m,i*2,pos,len,way);
upd(m+1,en,i*2+1,pos,len,way);
info[i]=info[i*2]+info[i*2+1];
}
node fans(int st,int en,int i,int l,int r){
if(st>r||en<l)return node();
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}lis,lds;
node inc[200005];
node de[200005];
node ans;
vector<int>v;
long long binpow(long long a,long long b){
if(b==0)return 1;
if(b==1)return a;
if(b%2==0)return (binpow(a,b/2)*binpow(a,b/2))%md;
return (binpow(a,b/2)*binpow(a,b/2)*a)%md;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>ar[i],v.push_back(ar[i]);
sort(v.begin(),v.end());
int id=0;
for(int i=n;i>=1;i--){
id=lower_bound(v.begin(),v.end(),ar[i])-v.begin()+1;
inc[i]=lds.fans(1,n,1,id+1,n);
inc[i].l+=1;
de[i]=lis.fans(1,n,1,1,id-1);
de[i].l+=1;
//cerr<<id<<":\n";
//cerr<<inc[i].l<<" "<<inc[i].w<<"\n";
//cerr<<de[i].l<<" "<<de[i].w<<"\n\n";
lis.upd(1,n,1,id,de[i].l,de[i].w);
lds.upd(1,n,1,id,inc[i].l,inc[i].w);
}
//cerr<<"\n";
//cerr<<"\n";
long long left,way,l;
node temp;
for(int i=1;i<=n;i++){
left=n-(inc[i].l+de[i].l)+1;
//cerr<<"left:"<<left<<"\n";
way=binpow(2,left);
way=(way*inc[i].w*de[i].w)%md;
l=inc[i].l+de[i].l-1;
temp=node(l,way);
//cerr<<l<<" "<<way<<"\n";
ans=ans+temp;
}
cout<<ans.l<<" "<<ans.w;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
31580 KB |
Output is correct |
| 2 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 3 |
Correct |
5 ms |
31576 KB |
Output is correct |
| 4 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 5 |
Correct |
6 ms |
31560 KB |
Output is correct |
| 6 |
Correct |
5 ms |
31580 KB |
Output is correct |
| 7 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 8 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 9 |
Correct |
6 ms |
31576 KB |
Output is correct |
| 10 |
Correct |
6 ms |
31580 KB |
Output is correct |
| 11 |
Runtime error |
170 ms |
33244 KB |
Memory limit exceeded |
| 12 |
Runtime error |
147 ms |
33244 KB |
Memory limit exceeded |
| 13 |
Correct |
132 ms |
32732 KB |
Output is correct |
| 14 |
Runtime error |
178 ms |
33384 KB |
Memory limit exceeded |
| 15 |
Runtime error |
247 ms |
33240 KB |
Memory limit exceeded |
| 16 |
Runtime error |
283 ms |
33240 KB |
Memory limit exceeded |
| 17 |
Runtime error |
222 ms |
33348 KB |
Memory limit exceeded |
| 18 |
Runtime error |
226 ms |
33244 KB |
Memory limit exceeded |
| 19 |
Runtime error |
230 ms |
33496 KB |
Memory limit exceeded |
| 20 |
Runtime error |
222 ms |
33240 KB |
Memory limit exceeded |
