oj.uz

Submission #555590

# Submission time Handle Problem Language Result Execution time Memory
555590 2022-05-01T08:33:02 Z orientor A Huge Tower (CEOI10_tower) C++17
100 / 100
 135 ms 8784 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define lli long long int
#define pii pair<int,int>
#define pll pair<lli, lli>
#define fi first
#define se second
#define double long double
#define all(x) x.begin(),x.end()
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define sz(x) ((int)(x).size())
#define prs(x,y) x.find(y)!=x.end()
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define forn(i,n) for(int i=0;i<(n);i++)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key number of items strictly smaller find_by_order kth element of set(0-index)
#define gog(T,x) cout<<"Case #"<<T<<": "<<x<<"\n";
typedef complex<double> base;
namespace FFT {
	const double C_PI = acos(-1);
	void fft(vector <base> &a, bool invert) {
		int n = sz(a);
		for (int i = 0, j = 0; i<n; ++i) {
			if (i>j) swap(a[i], a[j]);
			for (int k = n >> 1; (j ^= k)<k; k >>= 1);
		}
		for (int len = 2; len <= n; len <<= 1) {
			double ang = 2 * C_PI / len*(invert ? -1 : 1);
			base wlen(cos(ang), sin(ang));
			for (int i = 0; i<n; i += len) {
				base w(1);
				for (int j = 0; j<len / 2; j++) {
					base u = a[i + j], v = a[i + j + len / 2] * w;
					a[i + j] = u + v;
					a[i + j + len / 2] = u - v;
					w *= wlen;
				}
			}
		}
		if (invert) {
			for (int i = 0; i<n; i++) a[i] /= n;
		}
	} // Convert by using res[i] = ((int)(fa[i].real() + (fa[i].real()>0 ? 0.5 : -0.5)));
}
const lli MD=1e9+9LL;
lli powa(lli x,lli y, lli m)
{
	lli ans=1;
	while(y>0)
	{
		if(y%2==1)
		{
			ans*=x;
			ans%=m;
		}
		y/=2;
		x=x*x;
		x%=m;
	}
	return ans%m;
}
template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    mint(int32_t value_, std::nullptr_t) : value(value_) {}
    explicit operator bool() const { return value; }
    inline mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }
    inline mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }
    inline mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }
    inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }
    inline bool operator == (mint<MOD> other) const { return value == other.value; }
    inline bool operator != (mint<MOD> other) const { return value != other.value; }
    inline mint<MOD> pow(uint64_t k) const { return mint<MOD>(powa(value, k, MOD), nullptr); }
    inline mint<MOD> inv() const { return mint<MOD>(powa(value, MOD-2, MOD), nullptr); }
    inline mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); }
    inline mint<MOD> & operator /= (mint<MOD> other) { return *this *= other.inv(); }
};
template <int32_t MOD> mint<MOD> operator + (int64_t value, mint<MOD> n) { return mint<MOD>(value) + n; }
template <int32_t MOD> mint<MOD> operator - (int64_t value, mint<MOD> n) { return mint<MOD>(value) - n; }
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> mint<MOD> operator / (int64_t value, mint<MOD> n) { return mint<MOD>(value) / n; }
template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }
std::mt19937 gen(std::chrono::system_clock::now().time_since_epoch().count());
#define FAC 0
lli fac[FAC+1];
lli invfac[FAC+1];
lli cnk(lli n, lli k) {
    return (fac[n] * invfac[n - k] % MD * invfac[k] % MD)%MD;
}
#define mnt mint<MD>
// First of all remove t in case of single test case
lli solve()
{
	int n,d;
	cin>>n>>d;
	vector<int> a(n);
	forn(i,n)
	{
		cin>>a[i];
	}
	sort(all(a));
	mnt ans = 1;
	for(int i=0;i<n;i++)
	{
		ans*=(upper_bound(all(a), a[i]+d)-a.begin()-i);
	}
	cout<<ans;
	return 0;
}
int main()
{
	    fac[0]=invfac[0]=1;
    for(int i=1;i<=FAC;i++)
    {
        fac[i]=(fac[i-1]*i)%MD;
    }
        invfac[FAC]=powa(fac[FAC],MD-2, MD);
	for(int i=FAC-1;i>=1;i--)
	{
		invfac[i] = invfac[i+1]*(i+1)%MD;
	}
	fast_io //REMOVE FOR interactive problems
	{
		solve();
	}

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 980 KB Output is correct
2 Correct 9 ms 980 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3724 KB Output is correct
2 Correct 50 ms 3732 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 8784 KB Output is correct
2 Correct 135 ms 8112 KB Output is correct