Submission #653766

#	Time	Username	Problem	Language	Result	Execution time	Memory
653766		GusterGoose27	Žarulje (COI15_zarulje)	C++11	0 / 100	95 ms	9296 KiB

zarulje

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MOD = 1e9+7;
const int MAXN = 2e5+4;
int powers[MAXN];
int dp[MAXN];
int int_open[MAXN];
int int_close[MAXN];
int ans[MAXN];
int fac[MAXN];
int facinv[MAXN];
pii cur_space[MAXN];
int n, q;

int expo(ll a, int b) {
	ll res = 1;
	while (b > 0) {
		if (b & 1) {
			res *= a;
			res %= MOD;
		}
		b >>= 1;
		a *= a;
		a %= MOD;
	}
	return res;
}

int c(int n, int k) {
	ll cur = fac[n];
	cur *= facinv[k];
	cur %= MOD;
	cur *= facinv[n-k];
	return (cur%MOD);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> q;
	n += 2;
	fac[0] = 1;
	ll cur = 1;
	facinv[0] = 1;
	for (int i = 1; i <= n; i++) {
		cur *= i;
		cur %= MOD;
		fac[i] = cur;
		facinv[i] = expo(fac[i], MOD-2);
	}
	powers[0] = 0;
	powers[n-1] = 0;
	vector<pii> proc_order;
	for (int i = 1; i < n-1; i++) {
		cin >> powers[i];
		assert(powers[i] > 0);
		proc_order.push_back(pii(powers[i], i));
	}
	fill(int_open, int_open+n, -1);
	fill(int_close, int_close+n, -1);
	int_open[0] = int_close[n-1] = 0;
	sort(proc_order.begin(), proc_order.end());
	set<int> completed_vals;
	dp[0] = dp[n-1] = 1;
	completed_vals.insert(0);
	completed_vals.insert(n-1);
	for (int r = 0; r < n-2;) {
		vector<int> to_add;
		vector<int> extra_consid;
		int l = r;
		while (r < n-2 && proc_order[l].first == proc_order[r].first) r++;
		for (int curr = l; curr < r;) {
			int curl = curr;
			auto it = completed_vals.upper_bound(proc_order[curl].second);
			int rp = *it;
			it--;
			int lp = *it;
			vector<int> cur_posses;
			while (curr < r && *completed_vals.upper_bound(proc_order[curr].second) == rp) {
				cur_posses.push_back(proc_order[curr].second);
				to_add.push_back(proc_order[curr].second);
				curr++;
			}
			cur_space[rp].first = cur_space[lp].second = cur_posses.size();
			extra_consid.push_back(lp);
			extra_consid.push_back(rp);
			for (int p = 0; p < cur_posses.size()-1; p++) {
				int i = cur_posses[p];
				int_open[i] = i;
				int_close[cur_posses[p+1]] = i;
				ll curdp = dp[lp];
				curdp *= c(cur_posses.size(), p+1);
				curdp %= MOD;
				dp[i] = curdp;
				curdp = dp[lp];
				curdp *= c(cur_posses.size()-1, p);
				curdp %= MOD;
				ans[i] = curdp;
			}
		}
		for (int m: extra_consid) {
			if (cur_space[m].first != 0 && cur_space[m].second != 0) {
				auto it = completed_vals.lower_bound(m);
				int lp = *(--it);
				ll curdp = dp[lp];
				curdp *= c(cur_space[m].first+cur_space[m].second, cur_space[m].first);
				curdp %= MOD;
				ans[m] = curdp;
			}
			cur_space[m] = pii(0, 0);
		}
		for (int v: to_add) completed_vals.insert(v);
	}
	vector<int> stck;
	stck.push_back(0);
	for (int i = 1; i < n-1; i++) {
		if (int_close[i] >= 0) stck.pop_back();
		if (!ans[i]) ans[i] = dp[stck.back()];
		if (int_open[i] >= 0) stck.push_back(int_open[i]);
	}
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		cout << ans[x] << "\n";
	}
}

Compilation message (stderr)

zarulje.cpp: In function 'int main()':
zarulje.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for (int p = 0; p < cur_posses.size()-1; p++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~

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