oj.uz

Submission #741046

# Submission time Handle Problem Language Result Execution time Memory
741046 2023-05-13T13:24:06 Z mannshah1211 A Huge Tower (CEOI10_tower) C++14
100 / 100
 285 ms 15948 KB 
// 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1436 KB Output is correct
2 Correct 22 ms 1440 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6576 KB Output is correct
2 Correct 111 ms 6584 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 15948 KB Output is correct
2 Correct 285 ms 15364 KB Output is correct