oj.uz

답안 #775629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775629 2023-07-06T16:28:06 Z RonTheprogrammer A Huge Tower (CEOI10_tower) C++17
100 / 100
 98 ms 8244 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <set>
#include <limits>
#include <string>
#include <deque>
#include <cassert>
#include <math.h>
#include <list>
#include<numeric>
#include<map>
#include<set>
//#include <bits/stdc++.h>

typedef long long ll;
const int maxn = 2e5 + 5;
const int MOD =(1e9 + 9);
const int INF = 1e9+1;
#define srt(a) sort(a.begin(),a.end());
#define rev(a) reverse(a.begin(),a.end());
#define eb(a) emplace_back(a);
#define nl "\n"

//typedef  {int, int} p;

using  namespace std;
/**/
struct DSU
{
	vector<int>parent;
	vector<int>size;

	void dsuinit(int n)
	{
		parent.resize(n);
		size.resize(n);
		for (int i = 0; i < n; i++)
		{
			make_set(i);
		}
	}

	int find_set(int v) {
		if (v == parent[v])
			return v;
		return parent[v] = find_set(parent[v]);
	}

	void make_set(int v)
	{
		parent[v] = v;
		size[v] = 1;
	}

	bool unite(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (size[a] < size[b])
				swap(a, b);
			parent[b] = a;
			size[a] += size[b];
			return true;
		}
		return false;
	}
};
int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e - 1);
}
int __gcd(int a, int b)
{
	if (b > a)
	{
		swap(a, b);
	}
	if (a % b == 0)
		return b;
	return __gcd(a, a % b);
}
ll __lcm(int a, int b)
{
	return ((ll)a *(ll)  b) / __gcd(a, b);
}
struct price {
	int cost, cnt;
	bool  operator < (const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
	bool compare(const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
};
struct range {
	int l, r, thief, change;
	bool operator <(const range& other) const
	{
		if (l == other.l)
			return r < other.r;
		return l < other.l;
	}

};
struct hole {
	int c1,  c2;
	ll w;
};
bool prime[5000001]{ false};


void solve() {
	int n,d; cin >> n>>d;
	vector<int> a(n);
	for (auto& p : a)
		cin >> p;
	srt(a);
	ll ans = 1,r=0;
	for (int i = 0; i < n; i++) {
		while (r < n - 1 && a[r + 1] - a[i] <= d)
		{
			r++;
		}
		ans = (ans * (r - i + 1)) % MOD;
	}

	cout << ans;

	
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	//freopen("wormsort.in", "r", stdin);
	//freopen("wormsort.out", "w", stdout);
	int t=1;

	while (t--)
		solve();
	return 0;

}
/**
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4




*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #10
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 7 ms 980 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 1236 KB Output is correct
2 Correct 37 ms 3744 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 2644 KB Output is correct
2 Correct 98 ms 8244 KB Output is correct