Submission #285008

#	Time	Username	Problem	Language	Result	Execution time	Memory
285008		arnold518	Žarulje (COI15_zarulje)	C++14	100 / 100	206 ms	47208 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 4e5;
const int MOD = 1e9+7;
 
int N, A[MAXN+10], Q;
ll ans[MAXN+10];

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll t=mypow(x, y/2);
	return t*t%MOD;
}

ll fac[MAXN+10], ifac[MAXN+10];

ll invf(ll x, ll y)
{
	return ifac[x+y]*fac[x]%MOD*fac[y]%MOD;
}

ll f(ll x, ll y)
{
	return fac[x+y]*ifac[x]%MOD*ifac[y]%MOD;
}

vector<pii> V1[MAXN+10], V2[MAXN+10];

int P1[MAXN+10], P2[MAXN+10];

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
 
	fac[0]=1;
	for(int i=1; i<=MAXN; i++) fac[i]=fac[i-1]*i%MOD;
	ifac[MAXN]=mypow(fac[MAXN], MOD-2);
	for(int i=MAXN; i>=1; i--) ifac[i-1]=ifac[i]*i%MOD;

	{
		vector<int> S;
		for(int i=1; i<=N; i++)
		{
			while(!S.empty() && S.back()>A[i])
			{
				V1[i].push_back({S.back(), -1});
				S.pop_back();
			}
			V1[i].push_back({A[i], 1});
			S.push_back(A[i]);
		}
	}
	{
		vector<int> S;
		for(int i=N; i>=1; i--)
		{
			while(!S.empty() && S.back()>A[i])
			{
				V2[i].push_back({S.back(), 1});
				S.pop_back();
			}
			V2[i].push_back({A[i], -1});
			S.push_back(A[i]);
		}
		for(auto it : S) P2[it]++;
	}

	ll val=1;
	for(int i=1; i<=N; i++)
	{
		for(auto it : V1[i-1])
		{
			val=val*invf(P1[it.first], P2[it.first])%MOD;
			P1[it.first]+=it.second;
			val=val*f(P1[it.first], P2[it.first])%MOD;
		}
		for(auto it : V2[i])
		{
			val=val*invf(P1[it.first], P2[it.first])%MOD;
			P2[it.first]+=it.second;
			val=val*f(P1[it.first], P2[it.first])%MOD;
		}
		ans[i]=val;
	}

	while(Q--)
	{
		int p;
		scanf("%d", &p);
		printf("%lld\n", ans[p]);
	}
}

Compilation message (stderr)

zarulje.cpp: In function 'int main()':
zarulje.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
zarulje.cpp:41:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
zarulje.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |   scanf("%d", &p);
      |   ~~~~~^~~~~~~~~~

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