oj.uz

Submission #236017

# Submission time Handle Problem Language Result Execution time Memory
236017 2020-05-30T21:32:55 Z mahmoudbadawy Žarulje (COI15_zarulje) C++17
100 / 100
 337 ms 17404 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5,MOD=1e9+7;

int n,k;
int arr[N],ans[N];
int l[N],r[N];
stack<int> ll,rr;
vector<int> del[N];
long long fac[N],infac[N],anss;

long long poww(long long x,long long y)
{
	if(y==0) return 1;
	if(y&1) return (poww(x,y-1)*x)%MOD;
	return poww((x*x)%MOD,y/2);
}

long long nCk(int n,int k)
{
	return (((fac[n]*infac[k])%MOD)*infac[n-k])%MOD;
}

void add(int x,int dl,int dr)
{
	//cout << l[x]+r[x] << " " << l[x] << " " << poww(nCk(l[x]+r[x],l[x]),MOD-2) << endl;
	anss=(anss*poww(nCk(l[x]+r[x],l[x]),MOD-2))%MOD;
	l[x]+=dl; r[x]+=dr;
	//cout << l[x]+r[x] << " " << l[x] << " " << nCk(l[x]+r[x],l[x]) << endl;
	anss=(anss*nCk(l[x]+r[x],l[x]))%MOD;
}

int main()
{
	fac[0]=infac[0]=1; anss=1;
	for(int i=1;i<N;i++) {fac[i]=(i*fac[i-1])%MOD; infac[i]=poww(fac[i],MOD-2);}
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	for(int i=n-1;i>0;i--)
	{
		r[arr[i]]++;
		while(rr.size() && rr.top()>arr[i])
		{
			del[i].push_back(rr.top());
			r[rr.top()]--;
			rr.pop();
		}
		rr.push(arr[i]);
	}
	ans[0]=1;
	for(int i=1;i<n;i++)
	{
		while(ll.size() && ll.top()>arr[i-1])
		{
			add(ll.top(),-1,0);
			ll.pop();
		}
		ll.push(arr[i-1]);
		add(arr[i-1],1,0);
		add(rr.top(),0,-1);
		rr.pop();
		for(int j=del[i].size()-1;j>=0;j--)
		{
			rr.push(del[i][j]);
			add(del[i][j],0,1);
		}
		ans[i]=anss;
	}
	while(k--)
	{
		int x;
		scanf("%d",&x);
		x--;
		printf("%d\n",ans[x]);
	}
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
zarulje.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~
zarulje.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8184 KB Output is correct
2 Correct 50 ms 8184 KB Output is correct
3 Correct 52 ms 8312 KB Output is correct
4 Correct 52 ms 8188 KB Output is correct
5 Correct 51 ms 8312 KB Output is correct
6 Correct 52 ms 8184 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 11000 KB Output is correct
2 Correct 266 ms 13176 KB Output is correct
3 Correct 277 ms 13584 KB Output is correct
4 Correct 291 ms 13776 KB Output is correct
5 Correct 278 ms 14072 KB Output is correct
6 Correct 284 ms 14968 KB Output is correct
7 Correct 292 ms 15736 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8184 KB Output is correct
2 Correct 50 ms 8184 KB Output is correct
3 Correct 52 ms 8312 KB Output is correct
4 Correct 52 ms 8188 KB Output is correct
5 Correct 51 ms 8312 KB Output is correct
6 Correct 52 ms 8184 KB Output is correct
7 Correct 168 ms 11000 KB Output is correct
8 Correct 266 ms 13176 KB Output is correct
9 Correct 277 ms 13584 KB Output is correct
10 Correct 291 ms 13776 KB Output is correct
11 Correct 278 ms 14072 KB Output is correct
12 Correct 284 ms 14968 KB Output is correct
13 Correct 292 ms 15736 KB Output is correct
14 Correct 63 ms 8568 KB Output is correct
15 Correct 190 ms 12544 KB Output is correct
16 Correct 333 ms 16360 KB Output is correct
17 Correct 301 ms 15096 KB Output is correct
18 Correct 327 ms 16888 KB Output is correct
19 Correct 306 ms 15096 KB Output is correct
20 Correct 337 ms 16676 KB Output is correct
21 Correct 336 ms 17404 KB Output is correct