Submission #995174

#	Time	Username	Problem	Language	Result	Execution time	Memory
995174		vjudge1	Žarulje (COI15_zarulje)	C++17	100 / 100	462 ms	33108 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 10;
const ll MOD = 1e9 + 7;
ll a[N], ans[N], aft[N], prv[N];
vector <ll> add[N];
vector <ll> pos[N];
ll num_aft[N];
ll num_bef[N];
ll res = 1, fact[N], invfact[N];
ll binpow(ll x, ll n){
	x %= MOD;
	ll cur = 1;
	while (n > 0) {
		if (n % 2==1) {cur = cur * x % MOD;}

		x = x * x % MOD;
		n /= 2;
	}
	return cur;
}
void tinh(ll n){
	fact[0] = 1;
	invfact[0] = 1;
	for (int i = 1; i < n; i++) fact[i] = (fact[i - 1] * i) % MOD;
	for (int i = 1; i < n; i++) invfact[i] = binpow(fact[i], MOD - 2) % MOD;
}

ll choose(ll n, ll k){
	if (k == 0 || n == k) return 1;
	return (fact[n] * ((invfact[k] * invfact[n - k]) % MOD)) % MOD;
}
int main() {
	tinh(N);
	ll n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
        pos[a[i]].push_back(i);
	}

    stack<int> st;
    st.push(-1);
    for(int i = 0; i < n; i++) {
        while (st.size() > 1 && a[st.top()] >= a[i]) st.pop();
        num_bef[i] = upper_bound(pos[a[i]].begin(), pos[a[i]].end(), i) - lower_bound(pos[a[i]].begin(), pos[a[i]].end(), st.top());
        st.push(i);
    }
    while (!st.empty()) st.pop();
    st.push(n + 1);

    for (int i = n - 1; i >= 0; i--) {
        while (st.size() > 1 && a[st.top()] >= a[i]) st.pop();
        num_aft[i] = upper_bound(pos[a[i]].begin(), pos[a[i]].end(), st.top()) - lower_bound(pos[a[i]].begin(), pos[a[i]].end(), i);
        st.push(i);
    }
	stack<ll> end;
	for(int i = 0; i < n; i++) {
		while (!end.empty() && a[end.top()] > a[i]) end.pop();
		if (!end.empty()) add[end.top()].push_back(i);
		end.push(i);
	}

	for (auto val: add[0]) {
		aft[a[val]] = num_aft[val];
	}

	stack<ll> beg;
	ans[0] = 1;
	for(int i = 1; i < n; i++){
		while (!beg.empty() && a[beg.top()] >= a[i - 1]) {
			res = res * binpow(choose(aft[a[beg.top()]] + prv[a[beg.top()]], aft[a[beg.top()]]), MOD - 2) % MOD;
			prv[a[beg.top()]] = 0;
			beg.pop();
		}

		res = res * binpow(choose(aft[a[i -  1]] + prv[a[i - 1]], aft[a[i - 1]]), MOD - 2) % MOD;
		prv[a[i - 1]] = num_bef[i - 1];
		res = res * choose(aft[a[i - 1]] + prv[a[i - 1]], aft[a[i - 1]]) % MOD;
		beg.push(i - 1);
		res = res * binpow(choose(aft[a[i]] + prv[a[i]], aft[a[i]]), MOD - 2) % MOD;
		aft[a[i]] = 0;
		for (auto val: add[i]) {
			res = res * binpow(choose(aft[a[val]] + prv[a[val]], prv[a[val]]), MOD - 2) % MOD;
			aft[a[val]] = num_aft[val];
			res = res * choose(aft[a[val]] + prv[a[val]], prv[a[val]]) % MOD;
		}

		ans[i]=res;

	}
	while (k--) {
		ll s;
		cin >> s;
		cout << ans[s-1] << "\n";
	}
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40