# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
899714 | ivaziva | A Huge Tower (CEOI10_tower) | C++17 | 1072 ms | 17696 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000009
#define MAXN 1000010
long long n,d;
long long niz[MAXN];
long long val[MAXN];
vector<long long> levo,desno;
void mergee(long long l,long long mid,long long r)
{
for (long long i=l;i<=mid;i++) levo.push_back(niz[i]);
for (long long i=mid+1;i<=r;i++) desno.push_back(niz[i]);
long long poz1=0,poz2=0;
long long poz=l;
while (poz1<levo.size() and poz2<desno.size())
{
if (levo[poz1]<desno[poz2])
{
niz[poz]=levo[poz1];
poz1++;poz++;
}
else
{
niz[poz]=desno[poz2];
poz2++;poz++;
}
}
while (poz1<levo.size())
{
niz[poz]=levo[poz1];
poz1++;poz++;
}
while (poz2<desno.size())
{
niz[poz]=desno[poz2];
poz2++;poz++;
}
levo.clear();desno.clear();
}
void mergesort(long long l,long long r)
{
if (l>=r) return;
long long mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
mergee(l,mid,r);
}
int main()
{
ios_base::sync_with_stdio(false);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>d;
for (long long i=1;i<=n;i++) cin>>niz[i];
mergesort(1,n);
for (long long i=1;i<=n;i++)
{
long long br=0;
for (long long j=i-1;j>=1;j--)
{
if (niz[i]-niz[j]<=d) br++;
else break;
}
val[i]=br;
}
long long ans=1;
for (long long i=1;i<=n;i++)
{
ans*=(val[i]+1);
if (ans>=MOD) ans%=MOD;
}
cout<<ans<<endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |