Submission #372452

#	Time	Username	Problem	Language	Result	Execution time	Memory
372452		ngpin04	Žarulje (COI15_zarulje)	C++14	100 / 100	369 ms	17644 KiB

zarulje

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

vector <int> val[N];
vector <int> f;
vector <int> g;

int cntl[N];
int cntr[N];
int ans[N];
int fac[2 * N];
int inv[2 * N];
int a[N];
int n,m,cur = 1;

int binpow(int n, int k) {
	int res = 1;

	for (; k; k >>= 1, n = (long long) n * n % mod)
		if (k & 1)
			res = (long long) res * n % mod;
	return res;
}

int calc(int i, int j) {
	return (long long) fac[i + j] * inv[i] % mod * inv[j] % mod;
}

void add(int cnt[], int pos, int val) {
	cur = (long long) cur * binpow(calc(cntl[pos], cntr[pos]), mod - 2) % mod; //assert(cur);
	cnt[pos] += val;
	cur = (long long) cur * calc(cntl[pos], cntr[pos]) % mod; //assert(cur);
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> a[i];	
	
	fac[0] = 1;
	for (int i = 1; i <= 2 * n; i++)
		fac[i] = (long long) fac[i - 1] * i % mod;

	inv[2 * n] = binpow(fac[2 * n], mod - 2);

	for (int i = 2 * n - 1; i >= 0; i--)
		inv[i] = (long long) inv[i + 1] * (i + 1) % mod;

	// for (int i = 0; i <= 2 * n; i++)
	// 	cout << fac[i] << " " << inv[i] << endl;
	// return 0;


	for (int i = n; i >= 1; i--) {
		while (g.size() && a[i] < a[g.back()]) {
			val[i].push_back(g.back());
			add(cntr, a[g.back()], -1);
			g.pop_back();
		}

		g.push_back(i);
		add(cntr, a[i], 1);
	}

	for (int i = 1; i <= n; i++) {
		add(cntr, a[i], -1);
		g.pop_back();

		while (val[i].size()) {
			g.push_back(val[i].back());
			add(cntr, a[val[i].back()], 1);
			val[i].pop_back();
		}

		// cout << "pos " << i << ": " << cur << endl;

		// for (int x : f)
		// 	cout << x << " ";
		// cout << endl;

		// for (int x : g)
		// 	cout << x << " ";
		// cout << endl;

		ans[i] = cur;

		while (f.size() && a[i] < a[f.back()]) {
			add(cntl, a[f.back()], -1);
			f.pop_back();
		}

		f.push_back(i);
		add(cntl, a[i], 1);
	}

	while (m--) {
		int pos;
		cin >> pos;
		cout << ans[pos] << "\n";
	}
	return 0;
}

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