Advertisement
madhukeshk3

Nominating Group Leaders - Hackerrank

Sep 1st, 2020
67
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pfin(a) printf("%d\n",a);
  5. #define pfln(a) printf("%lld\n",a);
  6. #define pfis(a) printf("%d ",a);
  7. #define pfls(a) printf("%lld ",a);
  8. #define sfi(a) scanf("%d",&a);
  9. #define sfl(a) scanf("%lld",&a);
  10. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  11. #define f(i,a,b) for(int i=a;i<b;i++)
  12. #define pb(a) push_back(a);
  13. #define mp(a,b) make_pair(a,b)
  14. #define ll long long
  15. #define F first
  16. #define S second
  17. #define vi vector<int>
  18. #define vc vector<char>
  19.  
  20. const ll mod=1e9+7;
  21. const int N=1e5+5;
  22. const int BLOCK=320;// length of BLOCK size
  23. const int BKLN=316;// Length of array of buckets
  24.  
  25. vi bckt[BKLN];// bckt denoted frequency of frequency array of that particular bucket
  26.  
  27. int arr[N];
  28.  
  29. struct util
  30. {
  31.     int l,r,x,idx;
  32. };
  33.  
  34. bool cmp(util a,util b)
  35. {
  36.     int val1=a.l/BLOCK;
  37.     int val2=b.l/BLOCK;
  38.  
  39.     if(val1!=val2)
  40.         return val1<val2;
  41.  
  42.     if(val1%2==1)
  43.         return a.r<b.r;
  44.  
  45.     return b.r>a.r;
  46. }
  47.  
  48. int freq[N];
  49.  
  50. void add(int idx)
  51. {
  52.     int bkt=arr[idx]/BLOCK;
  53.     bckt[bkt][freq[arr[idx]]]--;
  54.     freq[arr[idx]]++;
  55.     bckt[bkt][freq[arr[idx]]]++;
  56.     return;
  57. }
  58.  
  59. void remove(int idx)
  60. {
  61.     int bkt=arr[idx]/BLOCK;
  62.     bckt[bkt][freq[arr[idx]]]--;
  63.     freq[arr[idx]]--;
  64.     bckt[bkt][freq[arr[idx]]]++;
  65.     return;
  66. }
  67.  
  68. void solve()
  69. {
  70.     memset(freq,0,sizeof(freq));
  71.     f(i,0,BKLN+5)
  72.         bckt[i].clear();
  73.  
  74.     f(i,0,BKLN)
  75.         bckt[i].resize(N+5);
  76.  
  77.     int n;
  78.     sfi(n)
  79.  
  80.     f(i,0,n)
  81.         sfi(arr[i])
  82.  
  83.     int q;
  84.     sfi(q)
  85.  
  86.     util query[q];
  87.  
  88.     f(i,0,q)
  89.     {
  90.         sfi(query[i].l)
  91.         sfi(query[i].r)
  92.         sfi(query[i].x)
  93.         query[i].idx=i;
  94.     }
  95.  
  96.     sort(query,query+q,cmp);
  97.  
  98.     int mleft=0,mright=-1;
  99.  
  100.     int ans[q];
  101.     memset(ans,-1,sizeof(ans));
  102.  
  103.     f(i,0,q)
  104.     {
  105.         int left=query[i].l;
  106.         int right=query[i].r;
  107.  
  108.         while(mright<right)
  109.         {
  110.             mright++;
  111.             add(mright);
  112.  
  113.         }
  114.         while(mright>right)
  115.         {
  116.             remove(mright);
  117.             mright--;
  118.         }
  119.         while(mleft<left)
  120.         {
  121.             remove(mleft);
  122.             mleft++;
  123.         }
  124.         while(mleft>left)
  125.         {
  126.             mleft--;
  127.             add(mleft);
  128.         }
  129.  
  130.         f(j,0,BKLN)
  131.         {
  132.             if(bckt[j][query[i].x]>0)
  133.             {
  134.                 int l=j*BKLN;
  135.                 while(freq[l]!=query[i].x)
  136.                 {
  137.                     l++;
  138.                 }
  139.                 ans[query[i].idx]=l;
  140.                 break;
  141.             }
  142.         }        
  143.     }
  144.  
  145.     f(i,0,q)
  146.         pfin(ans[i])
  147.  
  148.     return;
  149. }
  150.  
  151. int main()
  152. {
  153.     int t;
  154.     sfi(t)
  155.  
  156.     while(t--)
  157.         solve();
  158.  
  159.     return 0;
  160. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement