Submission #1280249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280249		coquelic	A Huge Tower (CEOI10_tower)	C++20	100 / 100	108 ms	5192 KiB

tower

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include <array> 
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define double long double
#define int long long
#define lc u<<1
#define rc u<<1|1
#define endl "\n"
#define X first
#define Y second
//typedef unsigned long long ll;
typedef long long ll;
typedef pair<ll, ll> PII;
const long long N = 1e6 + 50, M = 2e5 + 5, INF = 0x3f3f3f3f;
const long long maxm = 1e18 + 5, maxn = 3e5 + 5;
//const ll maxm = LLONG_MAX;
//const long long mod = 998244353;
const ll mod = 1e9 + 9;


ll dx[] = { -1,0,1,0 };
ll dy[] = { 0,1,0,-1 };

//__builtin_popcountll();
//a.erase(unique(a.begin(),a.end()),a.end());//去重
//string demo = str.substr(ps,(r-l+1));//截取下标从ps开始的长度为len子串
//找第一次出现的字符的下标也用.find吧
//字符串陋习，尽可能这样获取子串，直接+=会t

ll exgcd(ll a, ll b, ll& x, ll& y);

inline ll gcd(ll a, ll b) {
    return b > 0 ? gcd(b, a % b) : a;
}

ll ksm(ll a, ll b, ll p) {
    ll base = a;
    ll ans = 1;
    while (b) {
        if (b & 1)ans *= base;
        ans %= p;
        base *= base; base %= p;
        b >>= 1;
    }
    return ans % p;
}

void KKLK(ll a, ll b, ll c, ll d) {
    cout << "[ " << a << "," << b << "," << c << "," << d << " ]" << endl;
}

/*
struct cmp {
    bool operator()(node a, node b) {
        return a.d > b.d;//表示小根堆
    }
};*/

ll n, d; vector<ll>a;

void solve() {
    cin >> n >> d;
    a.resize(n + 5); 
    for (int i = 1; i <= n; i++)cin >> a[i];
    sort(a.begin() + 1, a.begin() + 1 + n);

    ll ans = 1;

    for (int i = 2; i <= n; i++) {
        auto p = lower_bound(a.begin()+1, a.begin()+1+n, a[i] - d);
        ll ps = p - a.begin();
        ans *= (i - ps + 1);
        ans %= mod;
    }
    cout << ans << endl;
}

/*
1
3
1 0 2
*/

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll _t = 1; //cin >> _t;
    while (_t--)solve();
    return 0;
}

/*PonyHex*/
/*SilverWolf__*/


ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll temp = x;
    x = y;
    y = temp - (a / b) * y;
    return g;
}

• 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