fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mx 100005
  3. #define FILENAME "fulltest.txt"
  4.  
  5. using namespace std;
  6. int n, q;
  7. int counter[mx];
  8. int arr[mx];
  9. int start[mx];
  10. int st[3*mx];
  11. int getMid(int st, int ed)
  12. {
  13.     return st + (ed - st)/2;
  14. }
  15.  
  16. int getOcc(int ss, int se, int qs, int qe, int si)
  17. {
  18.     if (qs <= ss&& qe >= se)
  19.         return st[si];
  20.     if (se < qs || ss > qe)
  21.         return -1;
  22.     int mid = getMid(ss, se);
  23.     return max(getOcc(ss, mid, qs, qe, si*2+1), getOcc(mid+1, se, qs, qe, si*2+2));
  24. }
  25.  
  26. void build_(int ss, int se, int si)
  27. {
  28.      if (ss == se)
  29.      {
  30.          st[si] = counter[arr[ss]];
  31.          return;
  32.      }
  33.      int mid = getMid(ss, se);
  34.      int l = si*2+1;
  35.      int r = si*2+2;
  36.      build_(ss, mid, l);
  37.      build_(mid+1, se, r);
  38.      st[si] = max(st[l], st[r]);
  39. }
  40.  
  41. int main()
  42. {
  43.     while (scanf("%d", &n))
  44.     {
  45.         if (n == 0)
  46.             break;
  47.         scanf("%d", &q);
  48.         memset(st, 0, sizeof(st));
  49.         memset(counter, 0, sizeof(counter));
  50.         memset(start, 0, sizeof(start));
  51.         for (int i = 0; i< n; i++)
  52.         {
  53.             scanf("%d", &arr[i]);
  54.             counter[arr[i]]++;
  55.         }
  56.         int y = mx, k = 0;
  57.         for (int i = 0; i< n; i++)
  58.         {
  59.             if (y != arr[i])
  60.             {
  61.                 k = i;
  62.                 y = arr[i];
  63.             }
  64.             start[i] = k;
  65.         }
  66.         build_(0, n-1, 0);
  67.         for (int i = 0; i < q; i++)
  68.         {
  69.             int ans = 0, k = 0, f = 0, sc = 0, th = 0;
  70.             int qs, qe;
  71.             scanf("%d %d", &qs, &qe);
  72.             qs--;
  73.             qe--;
  74.             if (arr[qs] != arr[qe])
  75.             {
  76.                 k = start[qs] + counter[arr[qs]];
  77.                 f = k - qs;
  78.                 sc = qe - start[qe] + 1;
  79.                 ans = max(f, sc);
  80.                 if (k <= start[qe] - 1){
  81.                     th = getOcc(0, n-1, k, start[qe] - 1, 0);
  82.                     ans = max(ans, th);
  83.                 }
  84.                 printf("%d\n", ans);
  85.             }
  86.             else
  87.             {
  88.                 printf("%d\n", qe - qs + 1);
  89.             }
  90.  
  91.         }
  92.     }
  93. }
  94.  
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/HVw4Dd
language:
C++14 (gcc 8.3)
created:
8 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!