Submission #973959

#	Time	Username	Problem	Language	Result	Execution time	Memory
973959		vjudge1	Zoltan (COCI16_zoltan)	C++14	140 / 140	104 ms	17856 KiB

zoltan

#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 (stderr)

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]);
      |                        ~~~~~^~~~~~~~~~~~

• Subtask 1: 140 / 140