Advertisement
madhukeshk3

Sherlock and Subarray Queries-HackerRank

Aug 27th, 2020
97
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.  
  23. int arr[N];
  24. int n;
  25. int table[N][17];
  26.  
  27. void build()
  28. {
  29.     f(i,0,n)
  30.         table[i][0]=arr[i];
  31.  
  32.     f(j,1,17)  
  33.     {
  34.         for(int i=0;i+(1<<j)<=n;i++)
  35.         {
  36.             table[i][j]=max(table[i][j-1],table[i+(1<<(j-1))][j-1]);
  37.         }
  38.     }
  39.  
  40.     return;
  41. }
  42.  
  43. int query(int l,int r)
  44. {
  45.     int var=log2(r-l+1);
  46.  
  47.     int ans=max(table[l][var],table[r-(1<<var)+1][var]);
  48.  
  49.     return ans;
  50. }
  51.  
  52. void solve()
  53. {
  54.     int m;
  55.     sfi(n)
  56.     sfi(m)
  57.  
  58.     vi v[N];
  59.  
  60.     f(i,0,n)
  61.     {
  62.         sfi(arr[i])
  63.         v[arr[i]].pb(i)
  64.     }
  65.  
  66.     build();
  67.  
  68.     while(m--)
  69.     {
  70.         int l,r;
  71.         sfi(l)
  72.         sfi(r)
  73.  
  74.         l--;
  75.         r--;
  76.  
  77.         int mx=query(l,r);
  78.  
  79.         auto itr1=upper_bound(v[mx].begin(),v[mx].end(),r)-v[mx].begin();
  80.         auto itr2=upper_bound(v[mx].begin(),v[mx].end(),l-1)-v[mx].begin();
  81.  
  82.         cout<<itr1-itr2<<endl;
  83.     }
  84.  
  85.     return;
  86. }
  87.  
  88. int main()
  89. {
  90.     solve();
  91.  
  92.     return 0;
  93. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement