fork(4) download 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4. using namespace std;
  5.  
  6. #define all(x) x.begin(), x.end()
  7. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  8. #define fd(i,a,b) for(int i = (a); i >= (b); i--)
  9. #define mp make_pair
  10. #define faster_io() ios_base::sync_with_stdio(false)
  11. #define pb push_back
  12. #define pii pair<int,int>
  13. #define SZ(x) ((int)x.size())
  14. #define TRACE(x) cout << #x << " = " << x << "\n";
  15. #define vii vector<pair<int,int>>
  16.  
  17. const ll INF = 1000000005;
  18. const ll INFLL = 1000000000000000005ll;
  19. const ll MOD = 1000000007;
  20.  
  21. // --------------------------------------------------------------------------
  22.  
  23. const int RIGHT = 131072;
  24. const int SIZE = 265000;
  25.  
  26. int A[SIZE], L[SIZE], R[SIZE], M[SIZE];
  27. int N, Q;
  28.  
  29. void build(int n, int a, int b)
  30. {
  31.     if(a == b)
  32.     {
  33.         L[n] = R[n] = M[n] = 1;
  34.         return;
  35.     }
  36.  
  37.     int mid = (a+b) / 2;
  38.     build(2*n, a, mid);
  39.     build(2*n+1, mid+1, b);
  40.  
  41.     int sz = (b-a+1) / 2;
  42.     L[n] = L[2*n] == sz && A[mid] == A[mid+1] ? L[2*n] + L[2*n+1] : L[2*n];
  43.     R[n] = R[2*n+1] == sz && A[mid] == A[mid+1] ? R[2*n] + R[2*n+1] : R[2*n+1];
  44.     M[n] = max(max(max(M[2*n], M[2*n+1]), L[n]), R[n]);
  45.     if(A[mid] == A[mid+1]) M[n] = max(M[n], R[2*n] + L[2*n+1]);
  46. }
  47.  
  48. int query(int l, int r, int n, int a, int b)
  49. {
  50.     if(a > r || b < l) return 0;
  51.     if(a >= l && b <= r) return M[n];
  52.  
  53.     int mid = (a+b) / 2;
  54.     int ql = query(l, r, 2*n, a, mid);
  55.     int qr = query(l, r, 2*n+1, mid+1, b);
  56.  
  57.     if(r <= mid) return ql;
  58.     if(l > mid) return qr;
  59.  
  60.     int at_left = min(mid-l+1, R[2*n]);
  61.     int at_right = min(r-mid, L[2*n+1]);
  62.     int middle = A[mid] == A[mid+1] ? at_left + at_right : 0;
  63.     return max(max(ql,qr), middle);
  64. }
  65.  
  66. int main()
  67. {
  68.     while(true)
  69.     {
  70.         scanf("%d",&N);
  71.         if(!N) return 0;
  72.         scanf("%d",&Q);
  73.         f(i,1,N) scanf("%d",&A[i]);
  74.         build(1,1,RIGHT);
  75.         while(Q--)
  76.         {
  77.             int l,r;
  78.             scanf("%d%d",&l,&r);
  79.             printf("%d\n", query(l,r,1,1,RIGHT));
  80.         }
  81.     }
  82. }
  83.  
Success #stdin #stdout 0s 7480KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/s0q1AY
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!