Submission #571780

#TimeUsernameProblemLanguageResultExecution timeMemory
571780BlagojceA Huge Tower (CEOI10_tower)C++11
100 / 100
122 ms18564 KiB
#include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define st first #define nd second #define all(x) begin(x), end(x) #define pb push_back #define all(x) begin(x), end(x) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int mxn = 1e6+5; const ll inf = 1e18; const ld eps = 1e-13; const ll mod = 1e9 + 9; mt19937 _rand(time(0)); int n, k; int a[mxn]; ll fakt[mxn]; ll tot = 1; void solve(vector<int> v){ int p = 0; ll ans = 1; fr(i, 0, (int)v.size()){ while(v[i] - v[p] > k){ ++p; } ans = (ans * (i-p+1)) % mod; } tot = (tot*ans)%mod; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; fakt[0] = 1; fr(i, 1, n+1) fakt[i] = (fakt[i-1]*i)%mod; fr(i, 0, n){ cin >> a[i]; } sort(a, a + n); vector<int> v; fr(i, 0, n){ if(!v.empty() && a[i] - v.back() > k){ solve(v); v.clear(); } v.pb(a[i]); } solve(v); cout<<tot<<endl; return 0; }/* 1 3 2 3 -1*/
#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...