fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int main() {
  8.  
  9. 	int n,k;
  10. 	cin>>n>>k;
  11.  
  12. 	int a[n];
  13. 	for(int i=0;i<n;i++)
  14. 	{
  15. 		cin>>a[i];
  16. 	}
  17.  
  18. 	vector<int> V;
  19. 	for(int i=0;i<k;i++)
  20. 	{
  21. 		V.push_back(a[i]);
  22. 	}
  23.  
  24. 	sort(V.begin(),V.end());
  25. 	multiset<int> LS;
  26. 	multiset<int> RS;
  27. 	if(k%2 == 0)
  28. 	{
  29. 		for(int i=0;i<V.size()/2;i++)
  30. 		{
  31. 			LS.insert(V[i]);
  32. 		}
  33.  
  34. 		for(int i=V.size()/2;i<V.size();i++)
  35. 		{
  36. 			RS.insert(V[i]);
  37. 		}
  38. 		cout<<*LS.rbegin()<<" ";
  39. 		for(int i=k;i<n;i++)
  40. 		{
  41. 			if(LS.find(a[i-k]) != LS.end())
  42. 			{
  43. 				LS.erase(LS.find(a[i-k]));
  44. 				LS.insert(*RS.begin());
  45. 				RS.erase(RS.begin());
  46. 			}
  47. 			else if(RS.find(a[i-k]) != RS.end())
  48. 			{
  49. 				RS.erase(RS.find(a[i-k]));
  50. 			}
  51.  
  52. 			if(LS.size() > 0 && a[i] >= *(LS.rbegin()))
  53. 			{
  54. 				RS.insert(a[i]);
  55. 			}
  56. 			else
  57. 			{
  58. 				LS.insert(a[i]);
  59. 			}
  60.  
  61. 			if(LS.size() < RS.size())
  62. 			{
  63. 				LS.insert(*(RS.begin()));
  64. 				RS.erase(RS.begin());
  65. 			}
  66. 			else if(LS.size() > RS.size())
  67. 			{
  68. 				while((LS.size() - RS.size()) > 0)
  69. 				{
  70. 					RS.insert(*(LS.rbegin()));
  71. 					LS.erase(--LS.end());
  72. 				}
  73. 			}
  74.  
  75. 			//cout<<"LS.size()="<<LS.size()<<" RS.size()="<<RS.size()<<endl;
  76. 			cout<<*LS.rbegin()<<" ";
  77. 		}
  78. 	}
  79. 	else 
  80. 	{
  81. 		for(int i=0;i<V.size()/2+1;i++)
  82. 		{
  83. 			LS.insert(V[i]);
  84. 		}
  85.  
  86. 		for(int i=V.size()/2+1;i<V.size();i++)
  87. 		{
  88. 			RS.insert(V[i]);
  89. 		}
  90.  
  91. 		cout<<*LS.rbegin()<<" ";
  92. 		for(int i=k;i<n;i++)
  93. 		{
  94. 			if(LS.find(a[i-k]) != LS.end())
  95. 			{
  96. 				LS.erase(LS.find(a[i-k]));
  97. 				LS.insert(*RS.begin());
  98. 				RS.erase(RS.begin());
  99. 			}
  100. 			else if(RS.find(a[i-k]) != RS.end())
  101. 			{
  102. 				RS.erase(RS.find(a[i-k]));
  103. 			}
  104.  
  105. 			if(LS.size() > 0 && a[i] >= *(LS.rbegin()))
  106. 			{
  107. 				RS.insert(a[i]);
  108. 			}
  109. 			else
  110. 			{
  111. 				LS.insert(a[i]);
  112. 			}
  113.  
  114. 			if(LS.size() < RS.size())
  115. 			{
  116. 				LS.insert(*(RS.begin()));
  117. 				RS.erase(RS.begin());
  118. 			}
  119. 			else if(LS.size() > RS.size())
  120. 			{
  121. 				while((LS.size() - RS.size()) > 1)
  122. 				{
  123. 					RS.insert(*(LS.rbegin()));
  124. 					LS.erase(--LS.end());
  125. 				}
  126. 			}
  127.  
  128. 			//cout<<"LS.size()="<<LS.size()<<" RS.size()="<<RS.size()<<endl;
  129.  
  130. 			cout<<*LS.rbegin()<<" ";
  131. 		}
  132. 	}
  133.  
  134.  
  135. 	return 0;
  136. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
10 2
1 2 3 4 5 6 7 8 9 10
stdout
copy 
1 2 3 4 5 6 7 8 9
https://ideone.com/Mbr01C
language:
C++14 (gcc 8.3)
created:
5 days 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!