Submission #703238

#TimeUsernameProblemLanguageResultExecution timeMemory
703238ef10A Huge Tower (CEOI10_tower)C++17
100 / 100
273 ms11200 KiB
// 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 = 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) { lo++; while (a[hi] - a[lo] > D) { lo++; } } ret *= (hi - lo + 1); ret %= 1000000009; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...