제출 #1334153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1334153		iitprep3	A Huge Tower (CEOI10_tower)	C++20	100 / 100	90 ms	8784 KiB

tower

/** 
　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ
**/
#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>,__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update> ordered_set;

#define int long long
#define vi vector<long long>
#define vpi vector<pair<long long ,long long>>
#define msi multiset <long long> 
#define msp multiset < pair<long long ,long long>> 
#define si set <long long> 
#define sp set < pair<long long ,long long>> 
#define mp map<long long ,long long>
#define all(v) v.begin() , v.end()
#define frieren for(int i = 0; i < n ; i++)
#define s(v) sort(all(v))
int n,k,q ,m , testcase = 1;
string s;


void vi_in(vi &v, int l = n);
int ceill(int a , int b);
void test();





void solve()
{
  cin >> n >> k ; 
  vi v ; 
  vi_in(v); 
  s(v); 
  int out = 1 ; 
  int pt = 0 ; 
  int mod = 1e9 + 9 ;
  for (int i = 0; i < n; i++)
  {
    while (pt < n - 1 && v[pt +1 ] - v[i] <= k) pt++; 
    out = out*(pt - i + 1)%mod; 
    out %= mod; 
  }
  
  cout << out << endl; 

}


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);


    solve();

    return 0;
}
 
 
 
void test(){
  cin >> testcase;
  while (testcase--)
  {
    solve();
  }
}
void vi_in(vi &v, int l)
{
  for (int i = 0; i < l; i++)
  {
    int x ; cin >> x ;
    v.push_back(x);;
  }
}
int ceill(int a , int b){
  if(a%b) return a/b + 1; 
  return a/b; 
}

• 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