Submission #284983

#	Time	Username	Problem	Language	Result	Execution time	Memory
284983		arnold518	Žarulje (COI15_zarulje)	C++14	38 / 100	1096 ms	11768 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;
int V1[MAXN+10], V2[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 f(ll x, ll y)
{
	return fac[x+y]*ifac[x]%MOD*ifac[y]%MOD;
}

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;

	while(Q--)
	{
		int p;
		scanf("%d", &p);
		int v=987654321;
		for(int i=1; i<=MAXN; i++) V1[i]=V2[i]=0;
		for(int i=p-1; i>=1; i--)
		{
			if(v>=A[i]) V1[A[i]]++;
			v=min(v, A[i]);
		}
		v=987654321;
		for(int i=p+1; i<=N; i++)
		{
			if(v>=A[i]) V2[A[i]]++;
			v=min(v, A[i]);
		}

		ll ans=1;
		for(int i=1; i<=MAXN; i++) ans=ans*f(V1[i], V2[i])%MOD;
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

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

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