fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #define MAX 100005
  4. typedef long long int ll;
  5. ll BIT[MAX + 5];
  6. ll Total = 0;
  7. ll Q, type, v;
  8.  
  9. void Update(ll index, int value){
  10.  
  11. 	while(index < MAX){
  12.  
  13. 		BIT[index] += value;
  14. 		index = index + (index & (-index));
  15. 	}
  16. }
  17.  
  18. ll Sum(ll index){
  19.  
  20. 	ll ans = 0; 
  21.  
  22.     while (index > 0){
  23.  
  24.         ans += BIT[index]; 
  25.         index = index - (index & (-index)); 
  26.     } 
  27.  
  28.     return ans;
  29. }
  30.  
  31. ll KthSmallest(ll k){ 
  32.  
  33.     ll l = 0; 
  34.     ll h = MAX; 
  35.     while (l < h){
  36.  
  37.         ll mid = (l + h) / 2; 
  38.         if (k <= Sum(mid)) 
  39.             h = mid; 
  40.         else
  41.             l = mid + 1; 
  42.     } 
  43.  
  44.     return l; 
  45. }
  46.  
  47. int main(){
  48.  
  49. 	cin >> Q;
  50.  
  51. 	for(int i = 1; i <= Q; i++){
  52.  
  53. 		cin >> type >> v;
  54.  
  55. 		if(type == 1 || type == 2){
  56.  
  57. 			if(type == 1){
  58.  
  59. 				Update(v, 1);	
  60. 				Total += 1;
  61. 			}
  62.  
  63. 			else{
  64.  
  65. 				Update(v, -1);
  66. 				Total -= 1;
  67. 			}
  68. 		}
  69.  
  70. 		else{
  71.  
  72. 			if(type == 3)	
  73. 				cout << KthSmallest(v) << endl;
  74.  
  75. 			else
  76. 				cout << KthSmallest(Total - v + 1) << endl;
  77.  
  78. 		}	
  79. 	}	
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 16016KB
comments (?)
stdin
copy 
10
1 1 
1 1
3 1
1 2
4 1
4 2
4 3
2 1
3 1
4 1
stdout
copy 
1
2
1
1
1
2
https://ideone.com/kSZyys
language:
C++14 (gcc 8.3)
created:
5 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!