fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct node{//Node and the values i want to store
  5.     int value;
  6.     int prefix;
  7.     int suffix;
  8.     int freq;
  9. };
  10.  
  11. void build(int n,int start,int end, int tree[],node arr[])
  12. {
  13.     /*This build function follows typical segment tree build for answering Range Maximum Query*/
  14.     if(start==end)
  15.         tree[n]=arr[start].freq;
  16.     else
  17.     {
  18.         int mid=(start+end)/2;
  19.         build(2*n+1,start,mid,tree,arr);
  20.         build(2*n+2,mid+1,end,tree,arr);
  21.         tree[n]= max(tree[2*n+1],tree[2*n+2]);
  22.     }
  23. }
  24. int query (int n, int start, int end, int l, int r, int tree[],node arr[])
  25. {
  26.     /*The query function is also typical one answering simple RMQ*/
  27.     if(l>r or start>end) return 0;
  28.     if(start>r or end<l) return 0;
  29.     else if(start>=l and end<=r)//Changing condition here to "if(start==end) removes WA, but gives TLE."
  30.     {
  31.         //cout<<"tree["<<n<<"] is "<<tree[n]<<endl;
  32.         return tree[n];
  33.     }
  34.     else
  35.     {
  36.         int mid=(start+end)/2,p=0,q=0;
  37.         //if(r>=start)
  38.         p=query(2*n+1,start,mid,l,r,tree,arr);
  39.         //if(l<=end)
  40.         q=query(2*n+2,mid+1,end,l,r,tree,arr);
  41.         return max(p,q);
  42.     }
  43. }
  44. int main() {
  45. 	// your code goes here
  46. 	ios_base::sync_with_stdio(0);//Fast input, Output
  47. 	cin.tie(NULL);
  48. 	cout.tie(NULL);
  49. 	while(true)
  50. 	{
  51. 	    int n,q;
  52. 	    cin>>n;
  53. 	    if(n==0)break;
  54. 	    cin>>q;
  55. 	    node arr[n];
  56. 	    int tree2[2*n+4];
  57. 	    int i,j,k;
  58. 	    for(i=0;i<n;i++)
  59. 	    {
  60. 	        cin>>arr[i].value;//An attempt to take input has been made here.
  61. 	    }
  62. 	    arr[0].prefix=0;
  63. 	    arr[n-1].suffix=n-1;
  64. 	    arr[0].freq=1;
  65. 	    for(i=1,j=n-2;i<n && j>=0;i++,j--)//The variable names are self-explanatory for the funtion.
  66. 	    {
  67. 	        if(arr[i].value==arr[i-1].value)
  68. 	            arr[i].prefix=arr[i-1].prefix;
  69. 	        else
  70. 	            arr[i].prefix=i;
  71. 	       if(arr[i].value==arr[i-1].value)
  72. 	            arr[i].freq=arr[i-1].freq+1;
  73. 	        else
  74.                 arr[i].freq=1;	  
  75.              if(arr[j].value==arr[j+1].value)
  76. 	            arr[j].suffix=arr[j+1].suffix;
  77. 	        else
  78. 	            arr[j].suffix=j;
  79.  
  80. 	    }
  81. 	    /*Below 4 loops were used in debugging, to check if things are working correctly till here.*/
  82. 	    //for(i=0;i<n;i++)cout<<arr[i].value<<" ";cout<<endl;
  83. 	    //for(i=0;i<n;i++)cout<<arr[i].prefix<<" ";cout<<endl;
  84. 	    //for(i=0;i<n;i++)cout<<arr[i].suffix<<" ";cout<<endl;
  85. 	    //for(i=0;i<n;i++)cout<<arr[i].freq<<" ";cout<<endl;
  86.  
  87.  
  88. 	    build(0,0,n-1,tree2,arr);//Build function to build the tree.
  89.  
  90.  
  91. 	   // for(i=0;i<2*n+4;i++)cout<<tree2[i]<<" ";cout<<endl;
  92. 	    while(q--)
  93. 	    {
  94. 	        int a,b;
  95. 	        cin>>a>>b;
  96. 	        a--,b--;
  97. 	        if(arr[a].prefix==arr[b].prefix)//If the range has a single block, eg-{1,1,1,1}
  98. 	            cout<<b-a+1<<"\n";
  99. 	       else if(arr[a].suffix+1==arr[b].prefix)//If range has only 2 blocks, eg- {1,1,1,2,2,2,2}
  100. 	            cout<<max(arr[a].suffix-a+1,b-arr[b].prefix+1)<<"\n";
  101. 	       else
  102. 	       {
  103. 	           int ans=max(arr[a].suffix-a+1,b-arr[b].prefix+1);
  104. 	           //cout<<"Ans and initial+final skip are "<<ans<<" "<<arr[a].suffix+1<<" "<<arr[b].prefix-1<<"\n";
  105. 	           //cout<<"The 2 choices were "<<arr[a].suffix-a+1<<" "<<b-arr[b].prefix+1<<"\n";
  106. 	           ans=max(ans,query(0,0,n-1,arr[a].suffix+1,arr[b].prefix-1,tree2,arr));
  107. 	           ans=max(ans,1);
  108. 	           cout<<ans<<"\n";
  109. 	       }
  110.  
  111. 	    }
  112. 	}
  113. 	return 0;
  114. }
  115.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
10 3
1 2 2 3 4 6 6 6 8 9
3 7
8 10
3 6
0
stdout
copy 
2
1
1
https://ideone.com/fJBxea
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!