oj.uz

Submission #285008

# Submission time Handle Problem Language Result Execution time Memory
285008 2020-08-28T08:52:08 Z arnold518 Žarulje (COI15_zarulje) C++14
100 / 100
 206 ms 47208 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;
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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25344 KB Output is correct
2 Correct 20 ms 25472 KB Output is correct
3 Correct 31 ms 25592 KB Output is correct
4 Correct 31 ms 25600 KB Output is correct
5 Correct 22 ms 25620 KB Output is correct
6 Correct 20 ms 25592 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 34424 KB Output is correct
2 Correct 123 ms 43072 KB Output is correct
3 Correct 120 ms 43308 KB Output is correct
4 Correct 133 ms 43512 KB Output is correct
5 Correct 116 ms 43768 KB Output is correct
6 Correct 117 ms 44536 KB Output is correct
7 Correct 206 ms 45304 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25344 KB Output is correct
2 Correct 20 ms 25472 KB Output is correct
3 Correct 31 ms 25592 KB Output is correct
4 Correct 31 ms 25600 KB Output is correct
5 Correct 22 ms 25620 KB Output is correct
6 Correct 20 ms 25592 KB Output is correct
7 Correct 76 ms 34424 KB Output is correct
8 Correct 123 ms 43072 KB Output is correct
9 Correct 120 ms 43308 KB Output is correct
10 Correct 133 ms 43512 KB Output is correct
11 Correct 116 ms 43768 KB Output is correct
12 Correct 117 ms 44536 KB Output is correct
13 Correct 206 ms 45304 KB Output is correct
14 Correct 31 ms 26496 KB Output is correct
15 Correct 124 ms 36028 KB Output is correct
16 Correct 154 ms 46232 KB Output is correct
17 Correct 137 ms 44920 KB Output is correct
18 Correct 160 ms 46712 KB Output is correct
19 Correct 144 ms 44920 KB Output is correct
20 Correct 172 ms 46260 KB Output is correct
21 Correct 169 ms 47208 KB Output is correct