Submission #1334963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1334963		sh_qaxxorov_571	A Huge Tower (CEOI10_tower)	C++20	100 / 100	214 ms	5260 KiB

tower

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll MOD = 1000000009; // Diqqat: Masalada 10^9 + 9 berilgan

int main() {
    int N;
    ll D;
    if (!(cin >> N >> D)) return 0;

    vector<ll> s(N);
    for (int i = 0; i < N; i++) {
        cin >> s[i];
    }

    // 1. Bloklarni saralaymiz
    sort(s.begin(), s.end());

    ll ans = 1;
    int j = 0;

    // 2. Har bir blok uchun mumkin bo'lgan o'rinlarni hisoblaymiz
    for (int i = 0; i < N; i++) {
        // s[i] dan s[j] ayirmasi D dan katta bo'lmaguncha j ni suramiz
        while (j < i && s[i] - s[j] > D) {
            j++;
        }
        
        // i - j + 1: bu s[i] bloki minoraning necha xil pozitsiyasida bo'lishi mumkinligi
        ans = (ans * (i - j + 1)) % MOD;
    }

    cout << ans << endl;

    return 0;
}

• 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