oj.uz

Submission #284983

# Submission time Handle Problem Language Result Execution time Memory
284983 2020-08-28T08:41:29 Z arnold518 Žarulje (COI15_zarulje) C++14
38 / 100
 1000 ms 11768 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 360 ms 9764 KB Output is correct
2 Correct 356 ms 9728 KB Output is correct
3 Execution timed out 1096 ms 9728 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10496 KB Output is correct
2 Correct 48 ms 10944 KB Output is correct
3 Correct 49 ms 11000 KB Output is correct
4 Correct 50 ms 11264 KB Output is correct
5 Correct 53 ms 11512 KB Output is correct
6 Correct 55 ms 11692 KB Output is correct
7 Correct 60 ms 11768 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 9764 KB Output is correct
2 Correct 356 ms 9728 KB Output is correct
3 Execution timed out 1096 ms 9728 KB Time limit exceeded
4 Halted 0 ms 0 KB -