Submission #90862

#	Time	Username	Problem	Language	Result	Execution time	Memory
90862		jasony123123	Žarulje (COI15_zarulje)	C++11	100 / 100	212 ms	38132 KiB

zarulje

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
/****************************************************************/

ll pow(ll a, ll p) {
	ll ret = 1LL;
	while (p) {
		if (p & 1LL)
			ret *= a;
		a *= a;
		ret %= MOD;
		a %= MOD;
		p >>= 1;
	}
	return ret;
}

ll inv(ll x) { // this give the modular inverse, albeit slowly
	x %= MOD;
	return pow(x, MOD - 2LL);
}

const int MAXN = 200099;
ll fact[MAXN], ifact[MAXN];

void precomp(int n) {
	fact[0] = 1;
	FORE(i, 1, n) fact[i] = ((ll)i*fact[i - 1]) % MOD;
	FORE(i, 0, n) ifact[i] = inv(fact[i]);
}
ll choose(int n, int r) {
	assert(n >= r);
	return (((fact[n] * ifact[n - r]) % MOD) * ifact[r]) % MOD;
}
ll invchoose(int n, int r) {
	assert(n >= r);
	return (((fact[r] * fact[n - r]) % MOD) * ifact[n]) % MOD;
}

int N, Q;
int A[MAXN];
int lcnt[MAXN], rcnt[MAXN];
v<pii> changes[MAXN];
ll allans[MAXN];

void initR() {
	// precompute right segments
	stack<int> st;
	RFORE(i, N - 1, 1) {
		while (!st.empty() && A[i] < st.top()) {
			changes[i].push_back({ st.top(), -1 });
			rcnt[st.top()]--;
			st.pop();
		}
		changes[i].push_back({ A[i], 1 });
		st.push(A[i]);
		rcnt[A[i]]++;
	}
}
int main() {
	io();
	cin >> N >> Q;
	FOR(i, 0, N) cin >> A[i];
	precomp(N);
	initR();

	allans[0] = 1;
	ll ans = 1;
	stack<int> stac;
	FOR(i, 1, N) {
		v<pii> lchanges;
		set<int> changedNums;

		// add [i-1] into left
		while (!stac.empty() && stac.top() > A[i - 1]) {
			lchanges.push_back({ stac.top(), -1 });
			changedNums.insert(stac.top());
			stac.pop();
		}
		lchanges.push_back({ A[i - 1], 1 });
		changedNums.insert(A[i - 1]);
		stac.push(A[i - 1]);

		// remove [i] from right
		for (pii &c : changes[i]) changedNums.insert(c.first);

		for (int x : changedNums) {
			ans *= invchoose(lcnt[x] + rcnt[x], lcnt[x]);
			ans %= MOD;
		}

		for (pii &c : lchanges) {
			lcnt[c.first] += c.second;
		}
		for (pii &c : changes[i]) {
			rcnt[c.first] -= c.second;
		}

		for (int x : changedNums) {
			ans *= choose(lcnt[x] + rcnt[x], lcnt[x]);
			ans %= MOD;
		}
		allans[i] = ans;
	}


	FOR(i, 0, Q) {
		int p;
		cin >> p;
		p--;
		cout << allans[p] << "\n";
	}

	return 0;
}

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