oj.uz

Submission #377251

# Submission time Handle Problem Language Result Execution time Memory
377251 2021-03-13T14:35:19 Z patrikpavic2 Žarulje (COI15_zarulje) C++17
100 / 100
 126 ms 15852 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 + 7;

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6636 KB Output is correct
2 Correct 8 ms 6636 KB Output is correct
3 Correct 8 ms 6636 KB Output is correct
4 Correct 8 ms 6636 KB Output is correct
5 Correct 8 ms 6636 KB Output is correct
6 Correct 8 ms 6636 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9068 KB Output is correct
2 Correct 69 ms 11628 KB Output is correct
3 Correct 68 ms 12012 KB Output is correct
4 Correct 72 ms 12140 KB Output is correct
5 Correct 73 ms 12396 KB Output is correct
6 Correct 78 ms 13292 KB Output is correct
7 Correct 82 ms 14188 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6636 KB Output is correct
2 Correct 8 ms 6636 KB Output is correct
3 Correct 8 ms 6636 KB Output is correct
4 Correct 8 ms 6636 KB Output is correct
5 Correct 8 ms 6636 KB Output is correct
6 Correct 8 ms 6636 KB Output is correct
7 Correct 39 ms 9068 KB Output is correct
8 Correct 69 ms 11628 KB Output is correct
9 Correct 68 ms 12012 KB Output is correct
10 Correct 72 ms 12140 KB Output is correct
11 Correct 73 ms 12396 KB Output is correct
12 Correct 78 ms 13292 KB Output is correct
13 Correct 82 ms 14188 KB Output is correct
14 Correct 14 ms 7020 KB Output is correct
15 Correct 64 ms 10860 KB Output is correct
16 Correct 116 ms 14848 KB Output is correct
17 Correct 96 ms 13548 KB Output is correct
18 Correct 124 ms 15596 KB Output is correct
19 Correct 100 ms 13548 KB Output is correct
20 Correct 125 ms 15084 KB Output is correct
21 Correct 126 ms 15852 KB Output is correct