fork download
copy 
  1. #include <stdio.h>
  2. int x[1000001],y[1000001];
  3. struct b
  4. {
  5. 	int summax;
  6. 	int summin;
  7. 	int diffmax;
  8. 	int diffmin;
  9. 	int l;
  10. 	int r;
  11. }a[10000000];
  12. int max(int a,int b)
  13. {
  14. 	if(a>b)
  15. 		return a;
  16. 	return b;
  17. }
  18. int min(int a,int b)
  19. {
  20. 	if(a>b)
  21. 		return b;
  22. 	return a;
  23. }
  24. //int counter=0;
  25. void create(int index,int l,int r)
  26. {
  27.  
  28. 	a[index].l=l;
  29. 	a[index].r=r;
  30. 	if(l==r)
  31. 	{
  32. 		a[index].summax=x[l]+y[l];
  33. 		a[index].diffmax=y[l]-x[l];
  34. 		a[index].summin=x[l]+y[l];
  35. 		a[index].diffmin=y[l]-x[l];
  36. 	}
  37. 	else
  38. 	{
  39. 		create(2*index,l,(l+r)/2);
  40. 		create(2*index+1,(l+r)/2+1,r);
  41. 		a[index].summax=max(a[2*index].summax,a[2*index+1].summax);
  42. 		a[index].summin=min(a[2*index].summin,a[2*index+1].summin);
  43. 		a[index].diffmax=max(a[2*index].diffmax,a[2*index+1].diffmax);
  44. 		a[index].diffmin=min(a[2*index].diffmin,a[2*index+1].diffmin);
  45. 	}
  46. 	return;
  47. }
  48. void update(int index,int in,int x,int y)
  49. {
  50. 	int l=a[index].l;
  51. 	int r=a[index].r;
  52. 	if(l==r)
  53. 	{
  54. 		if(r==in)
  55. 		{
  56. 			a[index].summax=x+y;
  57. 			a[index].diffmax=y-x;
  58. 			a[index].summin=x+y;
  59. 			a[index].diffmin=y-x;
  60. 		}
  61. 	return;
  62. 	}
  63. 	int mid=(l+r)/2;
  64. 	if(in<=mid)
  65. 	{
  66. 		update(2*index,in,x,y);
  67. 		a[index].summax=max(a[2*index].summax,a[2*index+1].summax);
  68. 		a[index].summin=min(a[2*index].summin,a[2*index+1].summin);
  69. 		a[index].diffmax=max(a[2*index].diffmax,a[2*index+1].diffmax);
  70. 		a[index].diffmin=min(a[2*index].diffmin,a[2*index+1].diffmin);
  71. 	}
  72. 	if(in>mid)
  73. 	{
  74. 		update(2*index+1,in,x,y);
  75. 		a[index].summax=max(a[2*index].summax,a[2*index+1].summax);
  76. 		a[index].summin=min(a[2*index].summin,a[2*index+1].summin);
  77. 		a[index].diffmax=max(a[2*index].diffmax,a[2*index+1].diffmax);
  78. 		a[index].diffmin=min(a[2*index].diffmin,a[2*index+1].diffmin);
  79. 	}
  80. 	return;
  81. }
  82. b make(b l,b r)
  83. {
  84. 	b temp;
  85. 	temp.summax=max(l.summax,r.summax);
  86. 	temp.summin=min(l.summin,r.summin);
  87. 	temp.diffmax=max(l.diffmax,r.diffmax);
  88. 	temp.diffmin=min(l.diffmin,r.diffmin);
  89. 	return temp;
  90. }
  91.  
  92. b ans(int index,int l2,int r2)
  93. {
  94. 	int l=a[index].l;
  95. 	int r=a[index].r;
  96. 	if(l>=l2&&r<=r2)
  97. 	{
  98. 		return a[index];
  99. 	}
  100. 	int mid=(l+r)/2;
  101. 	if(r2<=mid)
  102. 		return ans(2*index,l2,r2);
  103. 	else if (l2>mid)
  104. 		return ans(2*index+1,l2,r2);
  105. 	else
  106. 	{
  107. 		b temp=make(ans(2*index,l2,r2),ans(2*index+1,l2,r2));
  108. 		temp.l=l;
  109. 		temp.r=r;
  110. 		return temp;
  111. 	}
  112. }
  113. int main()
  114. {
  115. 	int n,i,m;
  116. 	scanf ("%d",&n);
  117.  
  118. 	for(i=0;i<n;i++)
  119. 	{
  120. 		scanf ("%d%d",&x[i],&y[i]);
  121. 	}
  122. 	create(1,0,n-1);
  123. 	scanf ("%d",&m);
  124. 	while (m--)
  125. 	{	
  126. 	//	for(int index=1;index<8;index++)
  127. 	//		printf ("%d %d %d %d %d %d\n",a[index].l,a[index].r,a[index].summax,a[index].summin,a[index].diffmax,a[index].diffmin);
  128. 		char tt[10];
  129. 		scanf ("%s",&tt);
  130. 		if(tt[0]=='U')
  131. 		{
  132. 			int x,y,in;
  133. 			scanf ("%d%d%d",&in,&x,&y);
  134. 			update(1,in,x,y);
  135. 		}
  136. 		else
  137. 		{
  138. 			int x,y;
  139. 			scanf ("%d%d",&x,&y);
  140. 			printf ("%d\n",max((ans(1,x,y).summax-ans(1,x,y).summin),(ans(1,x,y).diffmax-ans(1,x,y).diffmin)));
  141. 		}
  142. 	}
  143. 	return 0;
  144. }
Runtime error #stdin #stdout 0s 245504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DaJ9dV
language:
C++ (gcc 8.3)
created:
8 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!