Submission #923995

#	Time	Username	Problem	Language	Result	Execution time	Memory
923995		NintsiChkhaidze	A Huge Tower (CEOI10_tower)	C++17	100 / 100	99 ms	20244 KiB

tower

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 1e6 + 3,mod = 1e9 + 9;

int a[N],c[N];
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

    int n,D;
    cin>>n>>D;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sort(a+1,a+n+1);
    int r = n + 1;

    for (int i = n; i >= 1; i--){
        while (r - 1 >= 1 && a[i] <= a[r - 1] + D){
            --r;
        }
        c[i] = max(0LL,i - r);
    }

    int ans=1;
    for (int i= 1; i <= n; i++){
        ans = ans * (c[i] + 1) % mod;
    }
    cout<<ans<<endl;
}

• 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