제출 #365182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365182		kshitij_sodani	Žarulje (COI15_zarulje)	C++14	60 / 100	1059 ms	7916 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];


int le[200001];
int re[200001];
llo ee(llo aa,llo bb){
	if(bb==0){
		return 1;
	}
	llo ac=ee(aa,bb/2);
	ac=(ac*ac)%mod;
	if(bb%2==1){
		ac=(ac*aa)%mod;
	}
	return ac;
}
llo fac[1000001];
llo fac2[1000001];
llo cal(llo aa,llo bb){
	llo cur=(fac[aa]*fac2[aa-bb])%mod;
	cur=(cur*fac2[bb])%mod;
	return cur;
}

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]=ee(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<int,int>> ss;
	for(int i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a>it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		le[i]=-1;
		if(ss.size()){
			le[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
	ss.clear();

	for(int i=n-1;i>=0;i--){
		while(ss.size()){
			if(ss.back().a>it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		re[i]=-1;
		if(ss.size()){
			re[i]=ss.back().b;
		}
		ss.pb({it[i],i});
	}
/*	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	dp[0][n-1]=1;
	for(llo i=n-2;i>=0;i--){
		for(llo j=0;j+i<n;j++){
			dp[j][j+i]=0;
			llo x=0;
			if(j>0){
				x=max(x,it[j-1]);
			}
			if(j+i+1<n){
				x=max(x,it[j+i+1]);
			}
			if(j>0){
				if(it[j-1]==x){
					dp[j][j+i]+=dp[j-1][j+i];
				}
			}
			if(j+i+1<n){
				if(it[j+i+1]==x){
					dp[j][j+i]+=dp[j][j+i+1];
				}
			}
			dp[j][j+i]%=mod;
		}
	}*/
	//vector<llo> ss;
	for(llo i=0;i<k;i++){
		llo aa;
		cin>>aa;
		aa--;
	//	ss.pb(aa-1);
		map<int,pair<int,int>> tt;
		int cur=aa-1;
		while(cur>=0 and cur<n){
			if(tt.find(it[cur])!=tt.end()){
				tt[it[cur]].a++;
			}
			else{
				tt[it[cur]]={1,0};
			}
			//cout<<cur<<",,";
			cur=le[cur];
			

		}
		//cout<<endl;
		cur=aa+1;
		while(cur>=0 and cur<n){
			if(tt.find(it[cur])!=tt.end()){
				tt[it[cur]].b++;
			}
			else{
				tt[it[cur]]={0,1};
			}
			//cout<<cur<<",,";
			cur=re[cur];
		}
		//cout<<endl;
		int ans=1;
		for(auto j:tt){
			ans=(ans*cal(j.b.a+j.b.b,j.b.a))%mod;
		//	cout<<j.a<<":"<<j.b.a<<":"<<j.b.b<<endl;
		}
		cout<<ans<<endl;
	}
	/*for(auto j:ss){
		//cout<<dp[j][j]<<endl;
		map<int,int>


	}
*/






 
	return 0;
}

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