Submission #856584

#	Time	Username	Problem	Language	Result	Execution time	Memory
856584		beaboss	Žarulje (COI15_zarulje)	C++14	0 / 100	76 ms	19284 KiB

zarulje

// Source: https://oj.uz/problem/view/COI15_zarulje
// 

#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)
	return (fact[n] * ((invfact[k] * invfact[n - k]) % MOD)) % MOD;
}


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];
	}

	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);
		else {
			aft[a[i]] = num_aft[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[beg.top()] + prv[beg.top()], aft[beg.top()]), MOD-2) % MOD;
			prv[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;
		// cout << i << ' ' << res << endl;
		// 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;

	}

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


}

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