Submission #937730

#	Time	Username	Problem	Language	Result	Execution time	Memory
937730		amirhoseinfar1385	Zoltan (COCI16_zoltan)	C++17	140 / 140	238 ms	15304 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,mod=1e9+7;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}
long long n,all[maxn],len[maxn],dp[maxn];
struct node{
	int mx,ted;
	node(){
		mx=0;
		ted=1;
	}
}fakenode;
int kaf=(1<<18);

struct segment{
	node seg[(1<<19)];
	node merge(node a,node b){
		if(a.mx>b.mx){
			return a;
		}else if(b.mx>a.mx){
			return b;
		}
		a.ted+=b.ted;
		a.ted%=mod;
		if(a.mx==0){
			a.ted=1;
		}
		return a;
	}
	void upd(int i,int l,int r,int tl,int tr,node f){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]=merge(f,seg[i]);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,f);
		upd((i<<1)^1,m+1,r,tl,tr,f);
		seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
	}
	node pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return fakenode;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seginc,segdec;

void vorod(){
	cin>>n;
	vector<int>allind;
	for(long long i=0;i<n;i++){
		cin>>all[i];
		allind.push_back(all[i]);
	}
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	for(int i=0;i<n;i++){
		all[i]=lower_bound(allind.begin(),allind.end(),all[i])-allind.begin();
	}
}

void solve(){
	for(int i=n-1;i>=0;i--){
		node fdec=segdec.pors(1,0,kaf-1,all[i]+1,n+1);
		node finc=seginc.pors(1,0,kaf-1,0,all[i]-1);
		len[i]=fdec.mx+finc.mx+1;
		dp[i]=1ll*fdec.ted*finc.ted%mod;
		//cout<<i<<" "<<finc.mx<<" "<<finc.ted<<" "<<fdec.mx<<" "<<fdec.ted<<endl;
		finc.mx++;
		fdec.mx++;
		if(finc.mx==1){
			finc.ted=1;
		}
		if(fdec.mx==1){
			fdec.ted=1;
		}
		seginc.upd(1,0,kaf-1,all[i],all[i],finc);
		segdec.upd(1,0,kaf-1,all[i],all[i],fdec);
	}
}

void khor(){
	long long ted=0,res=0;
	for(int i=0;i<n;i++){
		if(len[i]==res){
			ted+=dp[i];
			ted%=mod;
		}else if(len[i]>res){
			res=len[i];
			ted=dp[i];
		}
	}
	//cout<<"wtf: "<<res<<" "<<ted<<endl;
	ted=1ll*ted*mypow(2,n-res)%mod;
	cout<<res<<" "<<ted<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

• Subtask 1: 140 / 140