fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4.     int n;
  5.     int arr[5010];
  6.     cin>>n;
  7.     for(int i=0;i<n;i++){
  8.         cin>>arr[i];
  9.     }
  10.     //for(int i=0;i<n;i++){
  11.     //    cout<<arr[i];
  12.     //}
  13.     int f[5010][5010];
  14.     for(int i=0;i<n;i++){
  15.       for(int j=0;j<n;j++){
  16.         f[i][j]=0;
  17.       }    
  18.     }
  19.     for(int i=0;i<n;i++){
  20.         //cout<<i;
  21.         //cout<<arr[i];
  22.         f[i][i] = arr[i];
  23.         //cout<<f[i][i];
  24.     }
  25.     //cout<<f[1][1];
  26.     for(int i=0;i<n-1;i++){
  27.         int answ = arr[i];
  28.         for(int j=i+1;j<n;j++){
  29.             answ = answ ^ arr[j];
  30.             if((j-i)%2==0){
  31.                 f[i][j] = arr[i] ^ arr[j];
  32.             }
  33.             else{
  34.                 f[i][j] = answ;
  35.             }
  36.         }
  37.     }
  38.     //cout<<f[1][1];
  39.     int ans[5010][5010];
  40.     for(int i=0;i<n;i++){
  41.       for(int j=0;j<n;j++){
  42.         ans[i][j]=0;
  43.       }
  44.     }
  45.     for(int i=0;i<n;i++){
  46.         ans[i][i] = arr[i];
  47.     }
  48.     // cout<<ans[0][0];
  49.     int maxrow[5010][5010];
  50.     for(int i=0;i<n;i++){
  51.       for(int j=0;j<n;j++){
  52.         maxrow[i][j]=0;
  53.       }
  54.     }
  55.     for(int i=0;i<n;i++){
  56.         maxrow[i][i] = arr[i];
  57.     }
  58.     //cout<<ans[0][0];
  59.     //cout<<maxrow[0][0];
  60.     //cout<<maxrow[0][1];
  61.      for(int j=1;j<n;j++){
  62.          // cout<<j<<" "<<j<<" ,";
  63.          int max = f[j][j];
  64.          // cout<<f[j][j];
  65.          for(int i=j-1;i>=0;i--){
  66.              // cout<<i<<" "<<j<<" ,";
  67.              if(f[i][j]>max){
  68.                  max = f[i][j];
  69.              }
  70.               maxrow[i][j] = max;
  71.              // cout<<maxrow[i][j];
  72.          }
  73.      }
  74.      //cout<<maxrow[0][1];
  75.      // cout<<"\n";
  76.      // for(int i=0;i<n;i++){
  77.      //   for(int j=0;j<n;j++){
  78.      //     cout<<f[i][j]<<" ";
  79.      //   }
  80.      //   cout<<"\n";
  81.      // }
  82.      // for(int i=0;i<n;i++){
  83.      //   for(int j=0;j<n;j++){
  84.      //     cout<<maxrow[i][j]<<" ";
  85.      //   }
  86.      //   cout<<"\n";
  87.      // }
  88.      // cout<<ans[0][0];
  89.      for(int i=0;i<n-1;i++){
  90.          for(int j=i+1;j<n;j++){
  91.              // cout<<i<<" "<<j<<"\n";
  92.              // cout<<i<<" "<<j-1<<"\n";
  93.              // cout<<ans[i][j];
  94.              //ans[i][j] = max(ans[i][j-1], maxrow[i][j]);
  95.              if(ans[i][j-1] > maxrow[i][j]){
  96.              	ans[i][j] = ans[i][j-1];
  97.              }
  98.              else{
  99.              	ans[i][j] = maxrow[i][j];
  100.              }
  101.          }
  102.      }
  103.      //ans[0][1] = max(ans[0][0], ans[0][1]);
  104.      //cout<<ans[0][1];
  105.      int q;
  106.      cin>>q;
  107.      int x,y;
  108.      // cout<<ans[0][0];
  109.      // cout<<f[0][0];
  110.      // for(int i=0;i<n;i++){
  111.      //   for(int j=0;j<n;j++){
  112.      //     cout<<ans[i][j]<<" ";
  113.      //   }
  114.      //   cout<<"\n";
  115.      // }
  116.      for(int i=0;i<q;i++){
  117.          cin>>x>>y;
  118.          // cout<<x<<"  "<<y<<endl;
  119.          cout<<ans[x-1][y-1]<<endl;
  120.      }
  121.      return 0;
  122. }
  123.  
Success #stdin #stdout 0s 4264KB
comments (?)
stdin
copy 
6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2
stdout
copy 
63
30
12
3
https://ideone.com/mpY9eM
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!