Advertisement
Saleh127

CodeChef Chef and Array-FRMQ / Sparse Table

Oct 8th, 2021
951
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. ///length of array = n ;
  6.  
  7. ll n,a[200005];
  8. ll st[200005][18];
  9. ll logg2[200005];
  10.  
  11. void logg()
  12. {
  13.     logg2[1]=0;
  14.  
  15.     for(ll i=2; i<=n; i++)
  16.     {
  17.         logg2[i]=logg2[i/2]+1;
  18.     }
  19. }
  20.  
  21.  
  22. void sparsetable()
  23. {
  24.     ll i,j,x,y;
  25.  
  26.     for(i=0; i<n; i++) st[i][0]=a[i];
  27.  
  28.     for(i=1; i<=logg2[n]; i++)
  29.     {
  30.         for(j=0; j+(1<<i)<=n; j++)
  31.         {
  32.             x=st[j][i-1];
  33.             y=st[j+(1<<i-1)][i-1];
  34.  
  35.             st[j][i]=max(x,y);
  36.         }
  37.     }
  38. }
  39.  
  40.  
  41. ll range_query(ll l,ll r)
  42. {
  43.     ll k=logg2[r-l+1];
  44.  
  45.     ll x=st[l][k];
  46.     ll y=st[r-(1<<k)+1][k];
  47.  
  48.     return max(x,y);
  49. }
  50.  
  51. int main()
  52. {
  53.     ios_base::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.  
  57.     ll i,j,k,l,q,ans=0,x,y;
  58.  
  59.     cin>>n;
  60.  
  61.     for(i=0; i<n; i++) cin>>a[i];
  62.  
  63.     logg();
  64.     sparsetable();
  65.  
  66.  
  67.     cin>>q>>j>>l;
  68.  
  69.     while(q--)
  70.     {
  71.  
  72.         x=min(j,l);
  73.         y=max(j,l);
  74.  
  75.         ans+=range_query(x,y);
  76.  
  77.         j+=7;
  78.  
  79.         if(j>=n-1) j%=(n-1);
  80.  
  81.         l+=11;
  82.  
  83.         if(l>=n) l%=n;
  84.     }
  85.  
  86.     cout<<ans<<endl;
  87.  
  88.     return 0;
  89. }
  90.  
  91.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement