oj.uz

Submission #365195

# Submission time Handle Problem Language Result Execution time Memory
365195 2021-02-11T08:03:12 Z kshitij_sodani Žarulje (COI15_zarulje) C++14
100 / 100
 697 ms 53996 KB 
//#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 19 ms 24044 KB Output is correct
4 Correct 19 ms 24044 KB Output is correct
5 Correct 20 ms 24172 KB Output is correct
6 Correct 21 ms 24172 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 33516 KB Output is correct
2 Correct 231 ms 43656 KB Output is correct
3 Correct 282 ms 43372 KB Output is correct
4 Correct 360 ms 43372 KB Output is correct
5 Correct 454 ms 43788 KB Output is correct
6 Correct 599 ms 48620 KB Output is correct
7 Correct 659 ms 51180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 19 ms 24044 KB Output is correct
4 Correct 19 ms 24044 KB Output is correct
5 Correct 20 ms 24172 KB Output is correct
6 Correct 21 ms 24172 KB Output is correct
7 Correct 206 ms 33516 KB Output is correct
8 Correct 231 ms 43656 KB Output is correct
9 Correct 282 ms 43372 KB Output is correct
10 Correct 360 ms 43372 KB Output is correct
11 Correct 454 ms 43788 KB Output is correct
12 Correct 599 ms 48620 KB Output is correct
13 Correct 659 ms 51180 KB Output is correct
14 Correct 31 ms 25068 KB Output is correct
15 Correct 214 ms 34668 KB Output is correct
16 Correct 266 ms 46572 KB Output is correct
17 Correct 299 ms 45548 KB Output is correct
18 Correct 401 ms 47084 KB Output is correct
19 Correct 470 ms 45776 KB Output is correct
20 Correct 631 ms 51308 KB Output is correct
21 Correct 697 ms 53996 KB Output is correct