oj.uz

Submission #377250

# Submission time Handle Problem Language Result Execution time Memory
377250 2021-03-13T14:34:52 Z patrikpavic2 Žarulje (COI15_zarulje) C++17
0 / 100
 40 ms 9452 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>

#define PB push_back

using namespace std;

typedef long long ll;

const int N = 2e5 + 500;
const int MOD = 1e9 + 9;

int fak[N], A[N], cnt[N][2], ans[N], n, q, inv[N];
stack < int > L, R;
vector < int > rek[N];

inline int add(int A, int B){
	if(A + B >= MOD)
		return A + B - MOD;
	return A + B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

inline int pot(int A, int B){
	int ret = 1, bs = A;
	for(; B ; B >>= 1){
		if(B & 1) ret = mul(ret, bs);
		bs = mul(bs, bs);
	}
	return ret;
}

void precompute(){
	fak[0] = 1, inv[0] = 1;
	for(int i = 1;i < N;i++){
		fak[i] = mul(fak[i - 1], i);
	}
	inv[N - 1] = pot(fak[N - 1], MOD - 2);
	for(int i = N - 2; i ; i--)
		inv[i] = mul(i + 1, inv[i + 1]);
}

int ch(int n, int k){
	return mul(fak[n], mul(inv[n - k], inv[k]));
}

int inv_ch(int n, int k){
	return mul(inv[n], mul(fak[n - k], fak[k]));
}

int sol = 1;

void promijeni(int x, int k, int del){
	sol = mul(sol,inv_ch(cnt[x][0] + cnt[x][1], cnt[x][0]));
	cnt[x][k] += del;
	sol = mul(sol, ch(cnt[x][0] + cnt[x][1], cnt[x][0]));
}

int main(){
	precompute();
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++)
		scanf("%d", A + i);
	for(int i = n - 1;i >= 0;i--){
		while(!R.empty() && R.top() > A[i])
			rek[i].PB(R.top()), promijeni(R.top(), 1, -1), R.pop();
		reverse(rek[i].begin(), rek[i].end());
		R.push(A[i]); promijeni(A[i], 1, 1);
	}
	for(int i = 0;i < n;i++){
		promijeni(R.top(), 1, -1); R.pop();
		for(int x : rek[i])
			R.push(x), promijeni(x, 1, 1);
		ans[i] = sol;
		while(!L.empty() && L.top() > A[i])
			promijeni(L.top(), 0, -1), L.pop();
		L.push(A[i]); promijeni(A[i], 0, 1);
	}
	for(;q--;){
		int x; scanf("%d", &x);
		printf("%d\n", ans[x - 1]);
	}
	return 0;
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
zarulje.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
zarulje.cpp:86:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |   int x; scanf("%d", &x);
      |          ~~~~~^~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6636 KB Output is correct
2 Correct 8 ms 6764 KB Output is correct
3 Incorrect 8 ms 6636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 9452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6636 KB Output is correct
2 Correct 8 ms 6764 KB Output is correct
3 Incorrect 8 ms 6636 KB Output isn't correct
4 Halted 0 ms 0 KB -