Contest Hunter 0601 Genius ACM

Genius ACM

Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all over the world.

As you may know, each batch of CPU chips must pass a quality test by the QC department before they can be sold. The testing procedure is as follows:

1) Randomly pick m pairs of CPU chips from the batch of chips (If there are less than 2m CPU chips in the batch of chips, pick as many pairs as possible.)

2) For each pair, measure the Relative Performance Difference (RPD) between the two CPU chips. Let D_i be the RPD of the i-th pair

3) Calculate the Sqared Performance Difference (SPD) of the batch according to the following formula:

SPD=∑D_i²

If there are only 1 CPU in a batch, then the SPD of that batch is 0.

4) The batch of chips pass the test if and only if SPD≤k, where k is a preseted constant

Usually they send all the n CPU chips as a single batch to the QC department every day. As one of the best CPU manufacturer in the world, ACM never fail the test. However, with the continuous improvement of CPU performance, they find that they are at risk!

Of course they don't want to take any risks. So they make a decision to divide the n chips into several batches to ensure all of them pass the test. What’s more, each batch should be a continuous subsequence of their productions, otherwise the QC department will notice that they are cheating. Quality tests need time and money, so they want to minimize the number of batches.

Given the absolute performance of the n chips P_{1 ...}P_n mesured by ACM in order of manufacture, your task is to determine the minimum number of batches to ensure that all chips pass the test. The RPD of two CPU chips equals to the difference of their absolute performance.

Input

The first line contains a single integer T, indicating the number of test cases.

In each test case, the first line contains three integers n, m, k. The second line contains n integers, P_{1 ...}P_n.

T≤12
1≤n,m≤5×10⁵
0≤k≤10¹⁸
0≤P_i≤2²⁰

Output

For each test case, print the answer in a single line.

Sample Input

Sample Output

2
1

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 //#include<queue>
  8 //#include<set>
  9 #define INF 0x3f3f3f3f
 10 #define N 500005
 11 #define re register
 12 #define Ii inline int
 13 #define Il inline long long
 14 #define Iv inline void
 15 #define Ib inline bool
 16 #define Id inline double
 17 #define ll long long
 18 #define Fill(a,b) memset(a,b,sizeof(a))
 19 #define R(a,b,c) for(register int a=b;a<=c;++a)
 20 #define nR(a,b,c) for(register int a=b;a>=c;--a)
 21 #define Min(a,b) ((a)<(b)?(a):(b))
 22 #define Max(a,b) ((a)>(b)?(a):(b))
 23 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 24 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 25 #define D_e(x) printf("
&__ %d __&
",x)
 26 #define D_e_Line printf("-----------------
")
 27 #define D_e_Matrix for(re int i=1;i<=n;++i){for(re int j=1;j<=m;++j)printf("%d ",g[i][j]);putchar('
');}
 28 using namespace std;
 29 Il read(){
 30     ll s=0,f=1;char c;
 31     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 32     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 33     return s*f;
 34 }
 35 Iv print(int x){
 36     if(x<0)putchar('-'),x=-x;
 37     if(x>9)print(x/10);
 38     putchar(x%10^'0');
 39 }
 40 /*
 41 Iv Count_Sort(int arr[]){
 42     int k=0;
 43     R(i,1,n)
 44         ++tot[arr[i]],Cmax(mx,a[i]);
 45     R(j,0,mx)
 46         while(tot[j])
 47             arr[++k]=j,--tot[j];
 48 }
 49 Iv Merge_Sort(int arr[],int left,int right,int &sum){
 50     if(left>=right)return;
 51     int mid=left+right>>1;
 52     Merge_Sort(arr,left,mid,sum),Merge_Sort(arr,mid+1,right,sum);
 53     int i=left,j=mid+1,k=left;
 54     while(i<=mid&&j<=right)
 55         arr[i]<=arr[j]?
 56             tmp[k++]=arr[i++]:
 57             tmp[k++]=arr[j++],sum+=mid-i+1;//Sum Is Used To Count The Reverse Alignment
 58     while(i<=mid)tmp[k++]=arr[i++];
 59     while(j<=right)tmp[k++]=arr[j++];
 60     R(i,left,right)arr[i]=tmp[i];
 61 }
 62 Iv Bucket_Sort(int arr[],int left,int right){
 63     int mx=0;
 64     R(i,left,right)
 65         Cmax(mx,arr[i]),++tot[arr[i]];
 66     ++mx;
 67     while(mx--)
 68         while(tot[mx]--)
 69             arr[right--]=mx;
 70 }
 71 */
 72 int n,m;
 73 ll maximum,a[N],tmp[N],tmp_2[N];
 74 Ib Jud(int l,int rp,int r){
 75     ll sum=0;
 76     R(i,rp+1,r)tmp[i]=a[i];
 77     sort(tmp+rp+1,tmp+r+1);
 78     merge(tmp+l,tmp+rp+1,tmp+rp+1,tmp+r+1,tmp_2+l);
 79     R(i,l,Min(l+r>>1,m+l-1)){
 80         sum+=(tmp_2[i]-tmp_2[l+r-i])*(tmp_2[i]-tmp_2[l+r-i]);
 81         if(sum>maximum)return 0;
 82     }
 83     if(sum<=maximum){
 84         R(i,l,r)
 85             tmp[i]=tmp_2[i];
 86         return 1;
 87     }
 88     return 0;
 89 }
 90 #define Outprint(x) print(x),putchar('
')
 91 int main(){
 92     int Test=read();
 93     while(Test--){
 94         int ans=0,l=1;
 95         n=read(),m=read(),maximum=read();
 96         R(i,1,n)
 97             a[i]=read();
 98         tmp[1]=a[1];
 99         while(l<=n){
100             int r=l,mov=1;//mov-> move step
101             while(mov)
102                 (r+mov<=n&&Jud(l,r,r+mov))?
103                     r+=mov,mov<<=1:
104                     mov>>=1;
105             l=r+1,++ans;
106         }
107         Outprint(ans);
108     }
109     return 0;
110 }

View Code