QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#829874#1264. Lower AlgorithmicsWorld_CreaterWA 469ms47188kbC++171.0kb2024-12-24 14:29:132024-12-24 14:29:14

Judging History

This is the latest submission verdict.

  • [2024-12-24 14:29:14]
  • Judged
  • Verdict: WA
  • Time: 469ms
  • Memory: 47188kb
  • [2024-12-24 14:29:13]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n,l,r,lim=1<<21,rev[3000005],ans;
complex<double> a[3000005],b[3000005];
const double pi=acos(-1),eps=1e-7;
void FFT(complex<double> a[],int inv)
{
	for(int i=0;i<=lim;i++)
	{
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	}
	for(int w=1;w<lim;w*=2)
	{
		complex<double> com(cos(pi/w),inv*sin(pi/w));
		for(int i=0;i<lim;i+=w*2)
		{
			complex<double> o(1,0);
			for(int j=0;j<w;j++)
			{
				complex<double> x=a[i+j],y=o*a[i+j+w];
				a[i+j]=x+y,a[i+j+w]=x-y;
				o*=com;
			}
		}
	}
}
int main()
{
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		a[x]=complex<double>(1,0);
	}
	for(int i=0;i<lim;i++)
	{
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=lim>>1;
	}
	FFT(a,1);
	for(int i=0;i<lim;i++)
	{
		if(fabs(a[i].imag())<eps&&fabs(a[i].real()-1)<eps) a[i]*=r-l+1;
		else a[i]=(pow(a[i],r+1)-pow(a[i],l))/(a[i]-(complex<double>(1,0)));
	}
	FFT(a,-1);
	for(int i=0;i<lim;i++)
	{
		if(fabs(a[i].real()/lim)>0.5) ans++;
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 221ms
memory: 47188kb

input:

2 1 2
1 2

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 221ms
memory: 47032kb

input:

3 1 3
1 3 10

output:

18

result:

ok answer is '18'

Test #3:

score: 0
Accepted
time: 227ms
memory: 47044kb

input:

6 3 5
1 2 3 4 5 6

output:

28

result:

ok answer is '28'

Test #4:

score: 0
Accepted
time: 223ms
memory: 46940kb

input:

3 1 3
1 3 4

output:

12

result:

ok answer is '12'

Test #5:

score: -100
Wrong Answer
time: 469ms
memory: 47188kb

input:

500 1 2000
6 8 9 10 11 14 16 19 23 24 25 30 31 33 34 38 44 46 48 49 52 53 55 56 58 60 64 65 68 69 70 71 72 74 75 77 79 81 83 84 88 89 93 95 98 103 105 108 109 110 111 118 119 120 121 123 125 129 130 132 134 136 137 138 140 141 144 149 154 155 159 160 161 163 165 166 169 170 172 173 174 175 176 177 1...

output:

0

result:

wrong answer expected '1999990', found '0'