Submission #989975

#TimeUsernameProblemLanguageResultExecution timeMemory
989975IdanRosenA Huge Tower (CEOI10_tower)C++98
100 / 100
99 ms8528 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MOD ((ll) 1e9 + 9) int main() { ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); ll n, d; cin >> n >> d; vector<ll> arr(n); for (auto &ref: arr) cin >> ref; // process the ans block by block, in increasing order of width std::sort(arr.begin(), arr.end()); // for the block of the current iteration, all the previous blocks are smaller than it meaning they can all be placed above it. // so our new answer will at least stay the same (not decrease). // but, in addition, if there are some k blocks which the new block can be placed above them (its size is not much bigger than theirs), // then there are another curr_ans * k possibilities for the new tower ll ans = 1; for (int i = 1; i < n; i++) { ll curr_width = arr[i]; ll start = 0; ll end = i; while (start < end) { ll mid = start + (end - start) / 2; if (arr[mid] + d < curr_width) start = mid + 1; else end = mid; } ll k = i - start; // the number of blocks which the new block can be placed above ans += (ans * k) % MOD; ans %= MOD; } cout << ans; }
#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...