fork download
copy 
  1. ///MAXIMUM SUM
  2.  
  3. #include <bits/stdc++.h>
  4. #define debug(x,y) cout<<"debug "<<x<<" "<<y<<endl;
  5. using namespace std;
  6.  
  7. int n,len,max1,max2,pos1;
  8. int arr[100002],acum[320],pos_max[320];
  9.  
  10. void find_max(int x){
  11. 	int maxi=0;
  12. 	for(int i=len*x;i<(x+1)*len;i++){
  13. 		if(maxi<arr[i]){
  14. 			maxi=arr[i];
  15. 			pos_max[x]=i;
  16. 		}
  17. 	}
  18. 	acum[x]=maxi;
  19. 	return;
  20. }
  21.  
  22. void update(int x,int value){
  23. 	arr[x]=value;
  24. 	find_max(x/len);
  25. 	return;
  26. }
  27.  
  28. int query(int l,int r){
  29. 	int sum=0,in=(l-1)/len,fin=(r-1)/len;
  30. 	if(r-l<len){
  31. 		for(int i=l;i<=r;i++){
  32. 			if(sum<arr[i]){
  33. 				sum=arr[i];
  34. 				pos1=i;
  35. 			}
  36. 		}
  37. 		return sum;
  38. 	}
  39. 	for(int i=l;i<in*len;i++){
  40. 		if(sum<arr[i]){
  41. 			sum=arr[i];
  42. 			pos1=i;
  43. 		}
  44. 	}
  45. 	for(in;in<fin;in++){
  46. 		if(sum<acum[in]){
  47. 			sum=acum[in];
  48. 			pos1=pos_max[in];
  49. 		}
  50. 	}
  51. 	for(int i=len*fin;i<=r;i++){
  52. 		if(sum<arr[i]){
  53. 			sum=arr[i];
  54. 			pos1=i;
  55. 		}
  56. 	}
  57. 	return sum;
  58. }
  59.  
  60. int main() {
  61. 	cin>>n;
  62. 	len=sqrt(n);
  63. 	for(int i=0;i<n;i++) scanf("%d",&arr[i]);
  64. 	for(int i=0;i<(n+len-1)/len;i++) find_max(i);
  65. 	int q,x,y;
  66. 	char c;
  67. 	scanf("%d",&q);
  68. 	int aux;
  69. 	while(q--){
  70. 		scanf(" %c %d%d",&c,&x,&y);
  71. 		if(c=='U'){
  72. 			update(x-1,y);
  73. 		} 
  74. 		else{
  75. 			max1=query(x-1,y-1);
  76. 			update(pos1,0);
  77. 			aux=pos1;
  78. 			//debug(pos1,max1)
  79. 			max2=query(x-1,y-1);
  80. 			//debug(pos1,max2)
  81. 			printf("%d\n",max1+max2);
  82. 			update(aux,max1);
  83. 		}
  84. 	}
  85. 	return 0;
  86. }
Runtime error #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4MXLGq
language:
C++ (gcc 8.3)
created:
4 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!