Advertisement
Guest User

Untitled

a guest
Apr 16th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4.  
  5. using namespace std;
  6. vector < vector <int> > spTAB_min;
  7. vector < vector <int> > spTAB_max;
  8.  
  9. void build_spTAB(vector <int> &arr){
  10.     int n = arr.size();
  11.     int k = (int)log2(n);
  12.  
  13.     for (int i = 0; i < n; i++){
  14.         spTAB_min[0][i] = arr[i];
  15.         spTAB_max[0][i] = arr[i];
  16.     }
  17.     for (int j = 1; j <= k; j++) {
  18.         for (int i = 0; i + pow(j, 2) <= n; i++) {
  19.             spTAB_min[j][i] = min (spTAB_min[j - 1][i], spTAB_min[j - 1][i + pow(j, 2)]);
  20.             spTAB_max[j][i] = max (spTAB_max[j - 1][i], spTAB_max[j - 1][i + pow(j, 2)]);
  21.         }
  22.     }
  23. }
  24.  
  25. int get_max(int R, int L){
  26.      int k = log2(R - L + 1);
  27.      cout << "MAX FROM " << R << " TO " << L << " = " << min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]) << endl;
  28.      return max(spTAB_max[k][L], spTAB_max[k][R - pow(k, 2) + 1]);
  29. }
  30.  
  31. int get_min(int R, int L){
  32.      int k = log2(R - L + 1);
  33.      cout << "MIN FROM " << R << " TO " << L << " = " << min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]) << endl;
  34.      return min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]);
  35. }
  36.  
  37. int main()
  38. {
  39.     int n;
  40.     cin >> n;
  41.  
  42.     vector <int> a(n);
  43.     spTAB_min.resize((int)log2(n)+1, vector <int> (n));
  44.     spTAB_max.resize((int)log2(n)+1, vector <int> (n));
  45.  
  46.     forn(i, n){
  47.         cin >> a[i];
  48.     }
  49.  
  50.     build_spTAB(a);
  51.  
  52.     int ans = 0, r = 0;
  53.  
  54.     for(int l = 0; l < n; l++){
  55.         while(r < n - 1 && get_max(l, r+1) - get_min(l, r+1) <= 1){
  56.             r++;
  57.         }
  58.         if(get_max(l, r) - get_min(l, r) <= 1){
  59.             ans = max(ans, r - l + 1);
  60.         }
  61.     }
  62.  
  63.     cout << ans;
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement