Advertisement
NgJaBach

Sparse Tablet

Jun 18th, 2020
210
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None
  1. /*
  2. Author: Ngbach2006
  3. */
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. typedef long long int ll;
  7. #define gcd __gcd
  8. const int N=400,M=100005;
  9. void ordinary_min(){
  10.     int i,j,n,dp[N][M],k,q,l,r,pawl;
  11.     cin>>n;
  12.     k=floor(log2(n));
  13.     for(i=0;i<n;++i) cin>>dp[0][i];
  14.     for(i=1;i<=k;++i){
  15.         for(j=0;j<n;++j){
  16.             pawl=j+(int)floor(pow(2,i-1));
  17.             if(pawl>=n) break;
  18.             dp[i][j]=min(dp[i-1][j],dp[i-1][pawl]);
  19.         }
  20.     }
  21.     cin>>q;
  22.     while(q--){
  23.         cin>>l>>r;
  24.         k=floor(log2(r-l+1));
  25.         cout<<min(dp[k][l],dp[k][r-(int)floor(pow(2,k))+1])<<endl;
  26.     }
  27. }
  28. void ordinary_max(){
  29.     int i,j,n,dp[N][M],q,l,r,pawl,k;
  30.     cin>>n;
  31.     k=floor(log2(n));
  32.     for(i=0;i<n;++i) cin>>dp[0][i];
  33.     for(i=1;i<=k;++i){
  34.         for(j=0;j<n;++j){
  35.             pawl=j+floor(pow(2,i-1));
  36.             if(pawl>=n) break;
  37.             dp[i][j]=max(dp[i-1][j],dp[i-1][pawl]);
  38.         }
  39.     }
  40.     cin>>q;
  41.     while(q--){
  42.         cin>>l>>r;
  43.         k=floor(log2(r-l+1));
  44.         cout<<max(dp[k][l],dp[k][r-(int)floor(pow(2,k))+1])<<endl;
  45.     }
  46. }
  47. int main(){
  48.     ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(NULL);
  49.    
  50.     return 0;
  51. }
  52. /*
  53. ==================================+
  54. INPUT:                            |
  55. ------------------------------    |
  56.  13
  57. 9 1 7 1 3 1 0 8 9 7 1 3 5
  58. 100
  59. 6 12
  60. ------------------------------    |
  61. ==================================+
  62. OUTPUT:                           |
  63. ------------------------------    |
  64.  
  65. ------------------------------    |
  66. ==================================+
  67. */
Advertisement
RAW Paste Data Copied
Advertisement