fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct node
  4. {
  5.   int res,pre,suf,pv,sv;
  6.   void merge(node a,node b)
  7.   {
  8.     pre = a.pre;
  9.     suf = b.suf;
  10.     pv = a.pv;
  11.     sv = b.sv;
  12.     if(a.pv == b.pv )
  13.       pre = a.pre + b.pre;
  14.     if(a.sv == b.sv)
  15.       suf = a.suf + b.suf;
  16.     res = max(a.res,b.res);
  17.     if(a.sv == b.pv)
  18.       res = max(res , a.suf + b.pre);
  19.   }
  20.     node(){
  21.       res = pre = suf = sv = pv = 0;
  22.     }
  23.     node(int val){
  24.       res = pre = suf = 1;
  25.       sv = pv = val;
  26.     }
  27. }tree[500000];
  28. void create(int pos)
  29. {
  30.   pos>>=1;
  31.   while(pos){
  32.     tree[pos].merge(tree[pos<<1],tree[(pos<<1)+1]);
  33.     pos>>=1;
  34.   }
  35. }
  36. node query(int root,int l_most,int r_most,int l,int r)
  37. {
  38.   if(l_most >= l && r_most <= r)
  39.     return tree[root];
  40.   int l_child = (root<<1) , r_child = l_child + 1,mid = (l_most + r_most )>>1;
  41.   node left=node(),right = node();
  42.   if(l<=mid)
  43.     left = query(l_child,l_most,mid,l,r);
  44.   if(r>mid)
  45.     right = query(r_child,mid+1,r_most,l,r);;
  46.   node temp = node();
  47.   temp.merge(left,right);
  48.   return temp;
  49. }
  50. int main()
  51. {
  52.   int n,c,t;
  53.   scanf("%d",&t);
  54.   while (t--){
  55. 	  scanf("%d %d",&n,&c);
  56. 	  int k = ceil(log(n)/log(2));
  57. 	  int pos = (1<<k),temp;
  58. 	  for(int i=0;i<c;i++){  
  59. 		  int x,p,q,v;
  60. 		  scanf("%d %d %d",&x,&p,&q);
  61. 		  if(x==0){
  62. 		  scanf("%d",&v);
  63. 			  for(int i=p-1;i<q;i++){
  64. 			    tree[pos+i] = node(v);
  65. 			    create(pos+i);
  66. 			  }
  67. 		  }
  68. 		  if(x==1){
  69. 		    printf("%d\n",query(1,1,pos,p,q).res);
  70. 		  }
  71. 	}
  72. 	}
  73.   return 0;
  74. }
Success #stdin #stdout 0s 12456KB
comments (?)
stdin
copy 
1
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8 
0 5 7 14
1 4 8
stdout
copy 
1
3
https://ideone.com/1Yb3yp
language:
C++ 4.3.2 (gcc-4.3.2)
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!