Submission #703110

#	Time	Username	Problem	Language	Result	Execution time	Memory
703110		ef10	A Huge Tower (CEOI10_tower)	C++17	15 / 100	1079 ms	11148 KiB

tower

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

long long N, D;

long long factor(long long n, long long m) {
	long long ret = 1;
	for (long long i = m; i <= n; i++) {
		ret *= i;
		ret %= 1000000009;
	}
	return ret;
}

long long solve(const vector<long long>& a, long long start, long long end) {
	if (start == end) return 1;
	long long ret = factor(end - start + 1, 1);
	//cout << "solve init: " << start << ", " << end << ", " << ret << endl;
	long long lo = start;
	long long hi = start + 1;
	while (hi <= end) {
		if (a[hi] - a[lo] > D) {
			ret -= (end - hi + 1) * factor(end - start, 1);
			//cout << "minus: " << end << ", " << hi << ", " << start << endl;
			lo++;
			while (a[hi] - a[lo] > D) {
				ret -= (end - hi + 1) * factor(end - start, 1);
				//cout << "minus: " << end << ", " << hi << ", " << start << endl;
				lo++;
			}
		}
		hi++;
	}
	//cout << "result: " << ret << endl;
	return ret;
}

int main() {
	cin >> N >> D;
	vector<long long> a(N);
	for (long long i = 0; i < N; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	long long start = 0;
	long long end = 0;
	long long total = 1;
	while (end < N -1) {
		if (a[end+1] - a[end] > D) {
			total *= solve(a, start, end);
			total %= 1000000009;
			end++;
			start = end;
			continue;
		}
		end++;
	}
	total *= solve(a, start, end);
	total %= 1000000009;
	cout << total << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5