fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7. 	public static void main (String[] args) throws java.lang.Exception
  8. 	{
  9. 		// your code goes here
  10. 		Scanner sc=new Scanner(System.in);
  11. 		int t=sc.nextInt();
  12. 		while(t-->0){
  13. 		    int n=sc.nextInt();
  14. 		    int k=sc.nextInt();
  15. 		    int l=sc.nextInt();
  16. 		    int r=sc.nextInt();
  17.  
  18. 		    int [] arr=new int [n+1];
  19. 		    for(int i=1;i<=n;i++){
  20. 		        arr[i]=sc.nextInt();
  21. 		    }
  22. 		    long countk = countU(arr, k, l) - countU(arr, k, r + 1);
  23.             long countk1 = countU(arr, k + 1, l) - countU(arr, k + 1, r + 1);
  24.  
  25.             long ans = countk - countk1;
  26.             System.out.println(ans);
  27.  
  28. 		}
  29. 		sc.close();
  30.  
  31. 	}
  32.  
  33. 	public static int solve(int [] arr, int k, int l, int r){
  34. 	    HashSet<Integer> set=new HashSet<>();
  35. 	    int n=arr.length;
  36. 	    int total=0;
  37. 	    int cnt=0;
  38. 	    int j=1;
  39.  
  40. 	    for(int i=1;i<n;i++){
  41. 	        while (j < n && cnt < k) {
  42. 	            if (!set.contains(arr[j])) cnt++;
  43. 	            j++;
  44. 	        }
  45. 	        if(cnt>=k){
  46. 	            total+= (n - (j - 1));
  47. 	        }
  48. 	        cnt--;
  49. 	    }
  50. 	    return total;
  51. 	}
  52.  
  53. 	public static int countU(int [] arr, int k,int u){
  54. 	    int n=arr.length;
  55. 	    int total=0;
  56.  
  57. 	    for (int i = 1; i < n; i++) {
  58.             Map<Integer, Integer> freq = new HashMap<>();
  59.             int j = i, distinct = 0, len = 0;
  60.  
  61.             while (j < n && (len < u || distinct < k)) {
  62.                 freq.put(arr[j], freq.getOrDefault(arr[j], 0) + 1);
  63.                 if (freq.get(arr[j]) == 1) distinct++; 
  64.                 j++;
  65.                 len = j - i;
  66.             }
  67.  
  68.             if (len >= u && distinct >= k) {
  69.                 total+=n-j+1;
  70.             }
  71.         }
  72. 	    return total;
  73. 	}
  74.  
  75. }
  76.  
Success #stdin #stdout 0.15s 54648KB
comments (?)
stdin
copy 
5
1 1 1 1
5
5 2 2 3
1 2 1 3 2
6 3 1 6
1 2 3 1 2 3
4 1 1 2
7 7 7 7
7 3 2 4
1 2 1 2 3 2 1
stdout
copy 
1
5
10
7
5
https://ideone.com/3h3d1J
language:
Java (HotSpot 12)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!