Submission #741046

#	Time	Username	Problem	Language	Result	Execution time	Memory
741046		mannshah1211	A Huge Tower (CEOI10_tower)	C++14	100 / 100	285 ms	15948 KiB

tower

// Master by November 2023

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

#define int long long
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define pb push_back
#define forn(i, n) for (int i = 0; i < n; i++)

int32_t main() {
   int n, d;
   cin >> n >> d;
   
   vector<int> a(n);
   for (int i = 0; i < n; i++) {
   	cin >> a[i];
   }
   
   sort(all(a));
   
   vector<int> b(n);
   int answer = 1;
   for (int i = 0; i < n; i++) {
   	int lo = 0, hi = i, ind = -1;
   	while (lo <= hi) {
   		int mid = (lo + hi) >> 1;
   		if (a[mid] >= a[i] - d) {
   			ind = mid;
   			hi = mid - 1;
   		} else {
   			lo = mid + 1;
   		}
   	}
   	answer *= (i - ind + 1);
   	answer %= (int) (1e9 + 9);
   }
   cout << answer << '\n';
}

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