oj.uz

Submission #856954

# Submission time Handle Problem Language Result Execution time Memory
856954 2023-10-05T01:16:43 Z beaboss Žarulje (COI15_zarulje) C++14
100 / 100
 215 ms 33176 KB 
// 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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21084 KB Output is correct
2 Correct 28 ms 19028 KB Output is correct
3 Correct 30 ms 21584 KB Output is correct
4 Correct 29 ms 19080 KB Output is correct
5 Correct 29 ms 21072 KB Output is correct
6 Correct 28 ms 19036 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 22832 KB Output is correct
2 Correct 193 ms 26604 KB Output is correct
3 Correct 177 ms 28476 KB Output is correct
4 Correct 168 ms 28908 KB Output is correct
5 Correct 171 ms 29520 KB Output is correct
6 Correct 171 ms 29148 KB Output is correct
7 Correct 177 ms 31600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21084 KB Output is correct
2 Correct 28 ms 19028 KB Output is correct
3 Correct 30 ms 21584 KB Output is correct
4 Correct 29 ms 19080 KB Output is correct
5 Correct 29 ms 21072 KB Output is correct
6 Correct 28 ms 19036 KB Output is correct
7 Correct 97 ms 22832 KB Output is correct
8 Correct 193 ms 26604 KB Output is correct
9 Correct 177 ms 28476 KB Output is correct
10 Correct 168 ms 28908 KB Output is correct
11 Correct 171 ms 29520 KB Output is correct
12 Correct 171 ms 29148 KB Output is correct
13 Correct 177 ms 31600 KB Output is correct
14 Correct 35 ms 21380 KB Output is correct
15 Correct 109 ms 24196 KB Output is correct
16 Correct 209 ms 31776 KB Output is correct
17 Correct 199 ms 29888 KB Output is correct
18 Correct 192 ms 32120 KB Output is correct
19 Correct 183 ms 28500 KB Output is correct
20 Correct 195 ms 32156 KB Output is correct
21 Correct 215 ms 33176 KB Output is correct