# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
973959 | vjudge1 | Zoltan (COCI16_zoltan) | C++14 | 104 ms | 17856 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |