Submission #653770

#	Time	Username	Problem	Language	Result	Execution time	Memory
653770		GusterGoose27	Žarulje (COI15_zarulje)	C++11	100 / 100	360 ms	21556 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 skip_dp[MAXN];
int ans[MAXN];
int fac[MAXN];
int facinv[MAXN];
pii cur_space[MAXN];
int n, q;

int bash(pii range) {
	if (range == pii(1, n-2)) return 1;
	if (powers[range.first-1] == powers[range.second+1])
		return (bash(pii(range.first-1, range.second))+bash(pii(range.first, range.second+1)) % MOD);
	if (powers[range.first-1] > powers[range.second+1]) return bash(pii(range.first-1, range.second));
	return bash(pii(range.first, range.second+1));
}

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

void solve() {
	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));
	}
	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;
		vector<int> skip_calc;
		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++;
			}
			if (rp < n-1) skip_calc.push_back(cur_posses.back());
			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(); p++) {
				int i = cur_posses[p];
				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;
				if (p < cur_posses.size()-1) {
					curdp = dp[lp];
					curdp *= c(cur_posses.size()-1, p+1);
					curdp %= MOD;
					skip_dp[i] = curdp;
				}
			}
		}
		for (int m: skip_calc) {
			auto it = completed_vals.lower_bound(m);
			int rp = *it;
			int lp = *(--it);
			ll curdp;
			if (powers[lp] >= powers[rp]) curdp = skip_dp[lp];
			else curdp = dp[lp];
			curdp *= c(cur_space[rp].first+cur_space[rp].second, cur_space[rp].first);
			skip_dp[m] = (curdp % MOD);
		}
		for (int v: extra_consid) cur_space[v] = pii(0, 0);
		for (int v: to_add) completed_vals.insert(v);
	}
	for (int i = 1; i < n-1; i++) {
		if (powers[i-1] < powers[i]) ans[i] = dp[i-1];
		else ans[i] = skip_dp[i-1];
	}
	bool fail = 0;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		// int b = bash(pii(x, x));
		cout << ans[x] << /*" " << b << */"\n";
		// if (b != ans[x]) fail = 1;
	}
	if (fail) cout << "FAIL\n";
}

void gen_case() {
	for (int i = 1; i <= n; i++) powers[i] = 1+(rand()%3);
}

int main() {
	solve();
	return 0;
	srand(time(0));
	while (1) {
		n = 10;
		gen_case();
		solve();
		for (int i = 1; i < n-1; i++) {
			int b = bash(pii(i, i));
			if (b != ans[i]) {
				for (int i = 0; i < n; i++) {
					cout << powers[i+1] << " ";
				}
				cout << endl;
				exit(0);
			}
		}
	}
}

Compilation message (stderr)

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

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