Submission #856954

#	Time	Username	Problem	Language	Result	Execution time	Memory
856954		beaboss	Žarulje (COI15_zarulje)	C++14	100 / 100	215 ms	33176 KiB

zarulje

// Source: https://oj.uz/problem/view/COI15_zarulje
// Use sets and stacks :|

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll N = 2e5 + 10;
const ll MOD = 1e9 + 7;
ll a[N];
ll ans[N];
ll aft[N];
ll prv[N];
vi add[N];

ll num_aft[N];
ll num_bef[N];

ll res = 1;

ll fact[N];
ll invfact[N];

ll binpow(ll x, ll n) { // binary exponentiation
	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 calcChoose(ll n) { // preprocessing
	fact[0]=1;
	invfact[0]=1;
	for (ll i = 1; i < n; i++) fact[i] = (fact[i-1]*i) % MOD;
	for (ll i = 1; i < n; i++) invfact[i] = binpow(fact[i], MOD - 2) % MOD;
}

ll choose(ll n, ll k) { // calculate choose in O(1)
	if (k == 0 || n == k) return 1;
	return (fact[n] * ((invfact[k] * invfact[n - k]) % MOD)) % MOD;
}

vi pos[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	calcChoose(N);
	ll n, k;
	cin >> n >> k;

	FOR(i, 0, n) {
		cin >> a[i];
        pos[a[i]].pb(i);
	}

    stack<int> st; // find previous lesser => increasing
    st.push(-1);

    FOR(i, 0, n) {
        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);
        // cout << i << ' ' << num_aft[i] << num_bef[i] << endl;
    }

	// ll cur = 1;
	// num_bef[0]=1;
	// FOR(i, 1, n) {
	// 	if (a[i] == a[i-1]) cur++;
	// 	else cur = 1;
	// 	num_bef[i]=cur;
	// }

	// cur = 1;
	// num_aft[n-1]=1;
	// for (ll i = n-2; i>= 0; i--) {
	// 	if (a[i] == a[i+1]) cur++;
	// 	else cur = 1;
	// 	num_aft[i]=cur;
	// }

	stack<ll> end;

	FOR(i, 0, n) { // non-decreasing stack to find previous <=
		while (!end.empty() && a[end.top()] > a[i]) end.pop();

		if (!end.empty()) add[end.top()].pb(i);
		

		end.push(i);
	}

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

	stack<ll> beg; // strictly increasing
	ans[0] = 1;

	FOR(i, 1, n) {

		// add (i - 1) to the beginning

		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);

		
		// remove i from the end

		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