oj.uz

Submission #365182

# Submission time Handle Problem Language Result Execution time Memory
365182 2021-02-11T07:27:44 Z kshitij_sodani Žarulje (COI15_zarulje) C++14
60 / 100
 1000 ms 7916 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];


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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4076 KB Output is correct
2 Correct 29 ms 7280 KB Output is correct
3 Correct 29 ms 7276 KB Output is correct
4 Correct 30 ms 7404 KB Output is correct
5 Correct 32 ms 7532 KB Output is correct
6 Correct 33 ms 7788 KB Output is correct
7 Correct 35 ms 7916 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 18 ms 4076 KB Output is correct
8 Correct 29 ms 7280 KB Output is correct
9 Correct 29 ms 7276 KB Output is correct
10 Correct 30 ms 7404 KB Output is correct
11 Correct 32 ms 7532 KB Output is correct
12 Correct 33 ms 7788 KB Output is correct
13 Correct 35 ms 7916 KB Output is correct
14 Correct 24 ms 876 KB Output is correct
15 Correct 294 ms 5484 KB Output is correct
16 Execution timed out 1059 ms 7664 KB Time limit exceeded
17 Halted 0 ms 0 KB -