답안 #937730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937730	2024-03-04T12:08:21 Z	amirhoseinfar1385	Zoltan (COCI16_zoltan)	C++17	140 / 140	238 ms	15304 KB

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.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	2 ms	12892 KB	Output is correct
4	Correct	3 ms	12888 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	3 ms	12924 KB	Output is correct
7	Correct	3 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12936 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	155 ms	14176 KB	Output is correct
12	Correct	124 ms	14096 KB	Output is correct
13	Correct	119 ms	14044 KB	Output is correct
14	Correct	166 ms	14144 KB	Output is correct
15	Correct	230 ms	14900 KB	Output is correct
16	Correct	238 ms	15304 KB	Output is correct
17	Correct	180 ms	14500 KB	Output is correct
18	Correct	201 ms	14524 KB	Output is correct
19	Correct	193 ms	14744 KB	Output is correct
20	Correct	204 ms	14732 KB	Output is correct