fork(3) download
copy 
  1. /*=================================*\
  2.     							   
  3. 	  Md. Shahidul Islam		   
  4. 		 CSE, BRUR				 
  5. 	  Rangpur, Bangladesh		  
  6.  mail: shahidul.cse.brur@gmail.com 
  7.  FB  : fb.com/shahidul.brur		
  8.  Blog: shahidul-brur.blogspot.com(in Bengali),
  9. 	   shahidul-brur-en.blogspot.com(in English) 
  10. \*=================================*/
  11. #include<bits/stdc++.h>
  12. using namespace std;
  13. const int MX = 100002;
  14. int ara[MX];
  15. struct Node
  16. {
  17.     int lVal, rVal;
  18.     int lCnt, rCnt;
  19.     int mxCnt;
  20. }node[4*MX];
  21. void build(int cur, int b, int e)
  22. {
  23.     if(b==e)
  24.     {
  25.         node[cur].lVal = node[cur].rVal = ara[b];
  26.         node[cur].lCnt = node[cur].rCnt = node[cur].mxCnt = 1;
  27.         return;
  28.     }
  29.     int m = (b+e)/2;
  30.     int L = cur*2;
  31.     int R = L+1;
  32.     build(L, b, m);
  33.     build(R, m+1, e);
  34.     node[cur].lVal = node[L].lVal;
  35.     node[cur].rVal = node[R].rVal;;
  36.     node[cur].lCnt = node[L].lCnt;
  37.     node[cur].rCnt = node[R].rCnt;
  38.     node[cur].mxCnt = max(node[L].mxCnt,node[R].mxCnt);
  39.  
  40.     if(node[L].rVal==node[R].lVal)
  41.     {
  42.         node[cur].mxCnt = max(node[cur].mxCnt, node[L].rCnt+node[R].lCnt);
  43.         if(node[L].lVal==node[L].rVal)
  44.             node[cur].lCnt += node[R].lCnt;
  45.         if(node[R].lVal==node[R].rVal)
  46.             node[cur].rCnt+=node[L].rCnt;
  47.     }
  48. }
  49. int query(int cur, int b, int e, int l, int r)
  50. {
  51.     if(r<b || l>e)
  52.         return -1;
  53.     if(b>=l && e<=r)
  54.     {
  55.         return node[cur].mxCnt;
  56.     }
  57.     int m = (b+e)/2;
  58.     int L = cur*2;
  59.     int R = L+1;
  60.     int qL = query(L, b, m, l, r);
  61.     int qR = query(R, m+1, e, l, r);
  62.     int ans = max(qL, qR);
  63.     if(node[L].rVal==node[R].lVal)
  64.     {
  65.         int lc, rc;
  66.         lc = min(m-l+1, node[L].rCnt);
  67.         rc = min(r-m, node[R].lCnt);
  68.         ans = max(ans, lc+rc);
  69.     }
  70.     return ans;
  71. }
  72. int main()
  73. {
  74.     //freopen("in.txt", "r", stdin);
  75.     int n, q;
  76.     while(scanf("%d",&n) && n!=0)
  77.     {
  78.         scanf("%d",&q);
  79.         for(int i=1;i<=n;i++)
  80.             scanf("%d",&ara[i]);
  81.         build(1, 1, n);
  82.         while(q--)
  83.         {
  84.             int l, r;
  85.             scanf("%d %d", &l, &r);
  86.             int ans = query(1, 1, n, l, r);
  87.            printf("%d\n", ans);
  88.         }
  89.     }
  90.     return 0;
  91. }
  92.  
Time limit exceeded #stdin #stdout 5s 4540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UOg6ss
language:
C++14 (gcc 8.3)
created:
6 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!