fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <cstring>
  5. using namespace std;
  6. pair<int,int> updateUtil(pair<int,int>* st,int i,int value,int i1,int j1,int id){
  7. 	if (i1==j1 && i1==i){
  8. 		st[id-1].first=value;
  9. 		st[id-1].second=value;
  10. 		return st[id-1];
  11. 	} 
  12. 	else if ((i1<i&&j1<i) || (i1>i && j1>i)) {
  13. 		return st[id-1];
  14. 	}
  15. 	pair<int,int> izq =updateUtil(st,i,value,i1,(i1+j1)/2,id*2),der= updateUtil(st,i,value,((i1+j1)/2)+1,j1,(id*2)+1);
  16. 	st[id-1].first= max(izq.first,der.first) ;
  17. 	st[id-1].second= min(izq.second,der.second) ;
  18. 	return st[id-1];
  19.  
  20. }
  21. void update(pair<int,int> * st,int i,int value,int n){
  22. 	updateUtil(st,i,value,1,n,1);
  23. }
  24. pair<int,int> getUtil(pair<int,int>* st,int i,int j,int i1,int j1,int id,bool x){//true mayor, false menor
  25. 	if (i1>=i && j1<=j) return st[id-1];
  26. 	else if ((i1<i&&j1<i) || (i1>j && j1>j)) {
  27. 		return make_pair(-1,99999999);
  28. 	}
  29. 	pair<int,int> izq=getUtil(st,i,j,i1,(i1+j1)/2,id*2,x),der= getUtil(st,i,j,((i1+j1)/2)+1,j1,(id*2)+1,x);
  30. 	return  make_pair(max(izq.first,der.first),min(izq.second,der.second));
  31. }
  32. pair<int,int> getRes(pair<int,int> * st,int i,int j,int n){
  33. 	return getUtil(st,i,j,1,n,1,true);
  34. }	
  35. pair<int,int> segmentTree(int * values,pair<int,int> * st,int i,int j,int id){
  36. 	if (i==j) {
  37. 		st[id-1].first=values[i-1];
  38. 		st[id-1].second=values[i-1];
  39. 		return st[id-1];
  40. 	}
  41. 	pair<int,int> izq =segmentTree(values,st,i,(i+j)/2,2*id),der= segmentTree(values,st,((i+j)/2)+1,j,(2*id)+1);
  42. 	st[id-1].first= max(izq.first,der.first) ;
  43. 	st[id-1].second= min(izq.second,der.second) ;
  44. 	return st[id-1];
  45.  
  46. }
  47. pair<int,int> * buildSegmentTree(int* ar,int size){
  48. 	int s = pow(2,ceil(log2(size))+1)-1;
  49. 	pair<int,int> *st = new pair<int,int>[s];
  50. 	segmentTree(ar,st,1,size,1);
  51. 	/*for (int i=0;i<s;i++){
  52. 		cout<<i<<" "<<st[i].first<<" "<<st[i].second<<endl;
  53.  
  54. 	}*/
  55. 	return st;
  56. }
  57.  
  58. int main(){
  59. 	int n,q;
  60. 	int in,fin,in2,fin2;
  61. 	char c;
  62. 	int ar [n][n];
  63. 	scanf("%d",&n);
  64. 	for (int i=0;i<n;i++){
  65. 		for (int j=0;j<n;j++){
  66. 			scanf("%d",&ar[j][i]);
  67. 		}
  68. 	}
  69. 	vector<pair<int,int> *> xs;
  70. 	int ma[n],me[n];
  71. 	pair<int,int> * mys,mns;
  72. 	for (int i=0;i<n;i++){
  73. 		xs.push_back(buildSegmentTree(ar[i],n));
  74. 		ma[i]=xs[i][0].first;
  75. 		me[i]=xs[i][0].second;
  76.  
  77. 	}
  78. 	scanf("%d",&q);
  79.  
  80. 	for (int i=0;i<q;i++){
  81. 		cin.ignore();
  82. 		scanf("%c %d %d %d",&c,&in,&fin,&in2);
  83. 		if (c=='c'){
  84. 			update(xs[fin-1],in,in2,n);	
  85. 		}
  86. 		else {
  87. 			scanf("%d",&fin2);
  88. 			pair<int,int>res = make_pair(-1,999999),aux;
  89. 			for (int j=fin-1;j<fin2;j++){
  90. 				//cout<<j<<" "<<fin<<" || "<<fin2<<endl;
  91. 				aux=getRes(xs[j],in,in2,n);
  92. 				res.first = max(res.first,aux.first);
  93. 				res.second = min(res.second,aux.second);
  94. 			}
  95. 			printf("%d %d\n",res.first,res.second);
  96. 		}
  97. 		//cout<<endl;
  98.  
  99. 	}
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
5
1 2 3 4 5
0 9 2 1 3
0 2 3 4 1
0 1 2 4 5
8 5 3 1 4
4
q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2
stdout
copy 
9 0
10 0
9 2
https://ideone.com/HmgsLK
language:
C++14 (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!