Submission #365195

#	Time	Username	Problem	Language	Result	Execution time	Memory
365195		kshitij_sodani	Žarulje (COI15_zarulje)	C++14	100 / 100	697 ms	53996 KiB

zarulje

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,k;
llo mod=1e9+7;
llo it[200001];
llo dp[2001][2001];


llo le[200001];
llo re[200001];
llo co[200001];
llo cot[200001];
llo cot2[200001];

llo eee(llo aa,llo bb){
	if(bb==0){
		return 1;
	}
	llo ac=eee(aa,bb/2);
	ac=(ac*ac)%mod;
	if(bb%2==1){
		ac=(ac*aa)%mod;
	}
	return ac;
}
llo fac[1000001];
llo fac2[1000001];
vector<pair<llo,llo>> pre[1000001];
llo cal(llo aa,llo bb){
	llo cur=(fac[aa]*fac2[aa-bb])%mod;
	cur=(cur*fac2[bb])%mod;
	return cur;
}
llo pp=1;
llo ans[1000001];
map<llo,llo> ee;
void add(llo x){
	pp=(pp*fac2[ee[x]])%mod;
	ee[x]++;
	pp=(pp*fac[ee[x]])%mod;
}

void rem(llo x){
	pp=(pp*fac2[ee[x]])%mod;
	ee[x]--;
	pp=(pp*fac[ee[x]])%mod;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;

	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	fac[0]=1;
	for(llo i=1;i<=n;i++){
		fac[i]=(fac[i-1]*i)%mod;
		//cout<<fac[i]<<":";
	}
//	cout<<endl;
	for(llo i=n;i<=n;i++){
		fac2[i]=eee(fac[i],mod-2);
		//cout<<fac2[i]<<":";
	}
 
	for(llo i=n-1;i>=0;i--){
		fac2[i]=(fac2[i+1]*(i+1))%mod;
	}
	vector<pair<llo,llo>> ss;
	for(llo i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a>it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		le[i]=-1;
		co[i]=1;
		if(ss.size()){
			le[i]=ss.back().b;
			if(ss.back().a==it[i]){
				co[i]+=co[ss.back().b];
			}
			cot[i]=((cot[ss.back().b]*eee(co[i],mod-2))%mod);
			//cot[i]=((cot[i]*fac[co[i]-1])%mod);
		}
		else{
			cot[i]=1;
		}
		ss.pb({it[i],i});
	}
	ss.clear();

	for(llo i=n-1;i>=0;i--){
		while(ss.size()){
			if(ss.back().a>it[i]){
				pre[i].pb(ss.back());
				ss.pop_back();
			}
			else{
				break;
			}
		}
		re[i]=-1;
		co[i]=1;
		if(ss.size()){
			re[i]=ss.back().b;
			if(ss.back().a==it[i]){
				co[i]+=co[ss.back().b];
			}
			cot2[i]=((cot2[ss.back().b]*eee(co[i],mod-2))%mod);
			//cot2[i]=((cot2[i]*fac[co[i]-1])%mod);
		}
		else{
			cot2[i]=1;
		}
		ss.pb({it[i],i});
	}
	vector<pair<llo,llo>> tt;
	for(llo i=0;i<n;i++){
		ee[it[i]]=0;
	}
	
	for(auto j:ss){
		add(j.a);
	}
	vector<pair<llo,llo>> xx;
	/*for(int i=0;i<n;i++){
		cout<<cot[i]<<":";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<cot2[i]<<":";
	}
	cout<<endl;
	for(int i=0;i<=n;i++){
		cout<<fac2[i]<<":";
	}
	cout<<endl;*/
	for(llo i=0;i<n;i++){

		rem(ss.back().a);
		ss.pop_back();
		if(pre[i].size()){
			reverse(pre[i].begin(),pre[i].end());
		}	
		for(auto j:pre[i]){
			ss.pb(j);
			add(j.a);
		}

		if(i>0){
			while(xx.size()){
				if(xx.back().a>it[i-1]){
					rem(xx.back().a);
					xx.pop_back();
				}
				else{
					break;
				}
			}
			add(it[i-1]);
			xx.pb({it[i-1],i});
		}
		llo ans2=pp;
		if(i>0){
			ans2=(ans2*cot[i-1])%mod;
		}
		if(i+1<n){
			ans2=(ans2*cot2[i+1])%mod;
		}
		ans[i]=ans2;
	}

	for(llo i=0;i<k;i++){
		llo aa;
		cin>>aa;
		aa--;
		cout<<ans[aa]<<endl;
	}


 
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40