fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	ios_base::sync_with_stdio(0);
  6. 	cin.tie(0);
  7. 	int n, m;
  8. 	cin >> n >> m;
  9. 	int n2=1;
  10. 	while(n2<n){
  11. 		n2*=2;
  12. 	}
  13. 	vector<pair<int, int>> v(2*n2);
  14. 	for(int i=n2+n; i<2*n2; i++){
  15. 		v[i].first=0;
  16. 		v[i].second=INT_MAX;
  17. 	}
  18. 	for(int i=n2; i<n2+n; i++){
  19. 		cin >> v[i].first;
  20. 		v[i].second=i;
  21. 	}
  22. 	for(int i=n2-1; i>0; i--){
  23. 		v[i].first=max(v[2*i].first, v[2*i+1].first);
  24. 		if(v[2*i].first>v[2*i+1].first){
  25. 			v[i].second = v[2*i].second;
  26. 		}
  27. 		else if(v[2*i].first<v[2*i+1].first){
  28. 			v[i].second = v[2*i+1].second;
  29. 		}
  30. 		else{
  31. 			v[i].second = min(v[2*i].first, v[2*i+1].first);
  32. 		}
  33. 	}
  34. 	for(int i=0; i<m; i++){
  35. 		string x;
  36. 		cin >> x;
  37. 		if(x=="PIORUN"){
  38. 			int a, b, c;
  39. 			cin >> a >> b >> c;
  40. 			a=a+n2-1;
  41. 			b=b+n2-1;
  42. 			int d=INT_MIN, e=INT_MAX;
  43. 			while(a<=b){
  44. 				if(a%2==1){
  45. 					if(v[a].first>d || (v[a].first==d && e>v[a].second)){
  46. 						e=v[a].second;
  47. 						d=v[a].first;
  48. 					}
  49. 					a++;
  50. 				}
  51. 				if(b%2==0){
  52. 					if(v[b].first>d || (v[b].first==d && e>v[b].second)){
  53. 						e=v[b].second;
  54. 						d=v[b].first;
  55. 					}
  56. 					b--;
  57. 				}
  58. 				a/=2;
  59. 				b/=2;
  60. 			}
  61. 			int p=e;
  62. 			v[p].first=max(v[p].first-c, 0);
  63. 			cout << p-n2+1 << " " << v[p].first << endl;
  64. 			v[p].second=p;
  65. 			while(p>0){
  66. 				v[p].first=max(v[2*p].first, v[2*p+1].first);
  67. 				if(v[2*p].first>v[2*p+1].first){
  68. 					v[p].second = v[2*p].second;
  69. 				}
  70. 				else if(v[2*p].first<v[2*p+1].first){
  71. 					v[p].second = v[2*p+1].second;
  72. 				}
  73. 				else{
  74. 					v[p].second = min(v[2*p].first, v[2*p+1].first);
  75. 				}
  76. 				p/=2;
  77. 			}
  78. 		}
  79. 		else if(x=="WZROST"){
  80. 			int a, b;
  81. 			cin >> a >> b;
  82. 			a=a+n2-1;
  83. 			int p=a/2;
  84. 			v[a].first+=b;
  85. 			while(p>0){
  86. 				v[p].first=max(v[2*p].first, v[2*p+1].first);
  87. 				if(v[2*p].first>v[2*p+1].first){
  88. 					v[p].second = v[2*p].second;
  89. 				}
  90. 				else if(v[2*p].first<v[2*p+1].first){
  91. 					v[p].second = v[2*p+1].second;
  92. 				}
  93. 				else{
  94. 					v[p].second = min(v[2*p].first, v[2*p+1].first);
  95. 				}
  96. 				p/=2;
  97. 			}
  98. 			cout << v[a].first << endl;
  99. 		}
  100. 	}
  101. 	return 0;
  102. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
6 5
3 0 5 7 2 1
PIORUN 5 6 3
WZROST 6 7
PIORUN 2 2 5
WZROST 2 1
PIORUN 2 5 3
stdout
copy 
5 0
8
2 0
1
4 4
https://ideone.com/zkNSya
language:
C++ (gcc 8.3)
created:
6 hours 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!