fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define X first
  4. #define Y second
  5. #define MP make_pair
  6. #define ll long long 
  7.  
  8. using namespace std;
  9.  
  10. const int N = 1e5 + 123;
  11.  
  12. struct node{
  13. 	node *left, *right;
  14. 	ll key, pr, size, tt;
  15. 	node(ll val){
  16. 		key = val;
  17. 		pr = rand() << 15;
  18. 		cout << pr << "\n";
  19. 		size = 1;
  20. 		tt = 0;
  21. 		left = right = nullptr;
  22. 	}
  23. };
  24.  
  25. int get_sz(node* v){
  26. 	return v == nullptr ? 0 : v->size;
  27. }
  28.  
  29. node* update(node* root){
  30. 	if(root == nullptr)
  31. 		return nullptr;
  32. 	root->size = get_sz(root->left) + get_sz(root->right) + 1;
  33. 	if(root->left != nullptr){
  34. 		root->left->key += root->tt;
  35. 		root->left->tt += root->tt;	
  36. 	}
  37. 	if(root->right != nullptr){
  38. 		root->right->key += root->tt;
  39. 		root->right->tt += root->tt;	
  40. 	}
  41. 	root->tt = 0;
  42. 	return root;
  43. }
  44.  
  45. pair<node*, node*> split(node* root, ll key){
  46. 	if(root == nullptr){
  47. 		return MP(nullptr, nullptr);
  48. 	}
  49. 	root = update(root);
  50. 	if(root->key >= key){
  51. 		pair<node*, node*> splitted = split(root->left, key);
  52. 		splitted.X = update(splitted.X);
  53. 		splitted.Y = update(splitted.Y);
  54. 		root->left = splitted.Y;                   
  55. 		root = update(root);
  56. 		return MP(splitted.X, root);
  57. 	}
  58. 	else{
  59. 		pair<node*, node*> splitted = split(root->right, key);
  60. 		splitted.X = update(splitted.X);
  61. 		splitted.Y = update(splitted.Y);
  62. 		root->right = splitted.X;
  63. 		root = update(root);
  64. 		return MP(root, splitted.Y);
  65. 	}
  66. }
  67.  
  68. node* insert(node* root, node* vertex){
  69. 	if(root == nullptr){
  70. 		return vertex;
  71. 	}
  72. 	root = update(root);
  73. 	cout << root->key << " -- " << vertex->key << "\n";
  74. 	if(root->pr > vertex->pr){
  75. 		if(root->key > vertex->key){
  76. 			root->left = insert(root->left, vertex);
  77. 			update(root->left);
  78. 		}
  79. 		else{
  80. 			root->right = insert(root->right, vertex);
  81. 			update(root->right);
  82. 		}
  83. 	}
  84. 	else{
  85. 		pair<node*, node*> splitted = split(root, vertex->key);
  86. 		splitted.X = update(splitted.X);
  87. 		splitted.Y = update(splitted.Y);
  88. 		vertex->left = splitted.X;
  89. 		vertex->right = splitted.Y;
  90. 		root = vertex;
  91. 	}
  92. 	root = update(root);
  93. 	return root;
  94. }
  95.  
  96. int n, k;
  97. ll a[N];
  98.  
  99. ll solve(ll val){
  100. 	node* root = nullptr;
  101. 	ll cnt = 0;
  102. 	for(int i = 1;i <= n;i++){
  103. 		if(i == 1){
  104. 			root = new node(a[1]);
  105. 		}
  106. 		else{
  107. 			root->tt += a[i], root->key += a[i];
  108. 			root = update(root);
  109. 			root = insert(root, new node(a[i]));
  110. 		}
  111. 		cout << val << " " << root->size << "\n";
  112. 		pair<node*, node*> splitted = split(root, val);
  113. 		if(splitted.Y != nullptr){
  114. 			cnt += splitted.Y->size;
  115. 		}
  116. 		cout << val << " " << root->size << "\n";
  117. 	}
  118. 	return cnt;
  119. }
  120.  
  121. int main () {
  122. 	ios::sync_with_stdio(0);
  123. 	cin.tie(0);
  124. 	cout.tie(0);
  125. 	srand(chrono::system_clock::now().time_since_epoch().count());
  126.  
  127.    	cin >> n >> k;
  128.    	for(int i = 1;i <= n;i++){
  129.    		cin >> a[i];
  130.    	}
  131.    	ll tl = -1e14 - 1, tr = 1e14 + 1;
  132.    	ll tp = 1e14;
  133.    	while(tl <= tr){
  134.    		ll tm = (tl + tr) / 2;
  135.    		ll cnt = solve(tm);
  136.    	//	cout << cnt << " " << tm << "\n";
  137.    		if(cnt < k){
  138.    			tr = tm - 1;
  139.    		}
  140.    		else{
  141.    			tl = tm + 1;
  142.    			tp = tm;
  143.    		}
  144.    	}
  145.    	cout << tp;
  146.    	return 0;
  147. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:3: error: illegal character: '#'
#define X first
^
Main.java:4: error: illegal character: '#'
#define Y second
^
Main.java:5: error: illegal character: '#'
#define MP make_pair
^
Main.java:6: error: illegal character: '#'
#define ll long long 
^
Main.java:10: error: class, interface, or enum expected
const int N = 1e5 + 123;
^
Main.java:12: error: class, interface, or enum expected
struct node{
^
Main.java:14: error: class, interface, or enum expected
	ll key, pr, size, tt;
	^
Main.java:15: error: class, interface, or enum expected
	node(ll val){
	^
Main.java:17: error: class, interface, or enum expected
		pr = rand() << 15;
		^
Main.java:18: error: class, interface, or enum expected
		cout << pr << "\n";
		^
Main.java:19: error: class, interface, or enum expected
		size = 1;
		^
Main.java:20: error: class, interface, or enum expected
		tt = 0;
		^
Main.java:21: error: class, interface, or enum expected
		left = right = nullptr;
		^
Main.java:22: error: class, interface, or enum expected
	}
	^
Main.java:25: error: class, interface, or enum expected
int get_sz(node* v){
^
Main.java:27: error: class, interface, or enum expected
}
^
Main.java:32: error: class, interface, or enum expected
	root->size = get_sz(root->left) + get_sz(root->right) + 1;
	^
Main.java:33: error: class, interface, or enum expected
	if(root->left != nullptr){
	^
Main.java:35: error: class, interface, or enum expected
		root->left->tt += root->tt;	
		^
Main.java:36: error: class, interface, or enum expected
	}
	^
Main.java:39: error: class, interface, or enum expected
		root->right->tt += root->tt;	
		^
Main.java:40: error: class, interface, or enum expected
	}
	^
Main.java:42: error: class, interface, or enum expected
	return root;
	^
Main.java:43: error: class, interface, or enum expected
}
^
Main.java:48: error: class, interface, or enum expected
	}
	^
Main.java:50: error: class, interface, or enum expected
	if(root->key >= key){
	^
Main.java:52: error: class, interface, or enum expected
		splitted.X = update(splitted.X);
		^
Main.java:53: error: class, interface, or enum expected
		splitted.Y = update(splitted.Y);
		^
Main.java:54: error: class, interface, or enum expected
		root->left = splitted.Y;                   
		^
Main.java:55: error: class, interface, or enum expected
		root = update(root);
		^
Main.java:56: error: class, interface, or enum expected
		return MP(splitted.X, root);
		^
Main.java:57: error: class, interface, or enum expected
	}
	^
Main.java:60: error: class, interface, or enum expected
		splitted.X = update(splitted.X);
		^
Main.java:61: error: class, interface, or enum expected
		splitted.Y = update(splitted.Y);
		^
Main.java:62: error: class, interface, or enum expected
		root->right = splitted.X;
		^
Main.java:63: error: class, interface, or enum expected
		root = update(root);
		^
Main.java:64: error: class, interface, or enum expected
		return MP(root, splitted.Y);
		^
Main.java:65: error: class, interface, or enum expected
	}
	^
Main.java:71: error: class, interface, or enum expected
	}
	^
Main.java:73: error: class, interface, or enum expected
	cout << root->key << " -- " << vertex->key << "\n";
	^
Main.java:74: error: class, interface, or enum expected
	if(root->pr > vertex->pr){
	^
Main.java:77: error: class, interface, or enum expected
			update(root->left);
			^
Main.java:78: error: class, interface, or enum expected
		}
		^
Main.java:81: error: class, interface, or enum expected
			update(root->right);
			^
Main.java:82: error: class, interface, or enum expected
		}
		^
Main.java:86: error: class, interface, or enum expected
		splitted.X = update(splitted.X);
		^
Main.java:87: error: class, interface, or enum expected
		splitted.Y = update(splitted.Y);
		^
Main.java:88: error: class, interface, or enum expected
		vertex->left = splitted.X;
		^
Main.java:89: error: class, interface, or enum expected
		vertex->right = splitted.Y;
		^
Main.java:90: error: class, interface, or enum expected
		root = vertex;
		^
Main.java:91: error: class, interface, or enum expected
	}
	^
Main.java:93: error: class, interface, or enum expected
	return root;
	^
Main.java:94: error: class, interface, or enum expected
}
^
Main.java:97: error: class, interface, or enum expected
ll a[N];
^
Main.java:99: error: class, interface, or enum expected
ll solve(ll val){
^
Main.java:101: error: class, interface, or enum expected
	ll cnt = 0;
	^
Main.java:102: error: class, interface, or enum expected
	for(int i = 1;i <= n;i++){
	^
Main.java:102: error: class, interface, or enum expected
	for(int i = 1;i <= n;i++){
	              ^
Main.java:102: error: class, interface, or enum expected
	for(int i = 1;i <= n;i++){
	                     ^
Main.java:105: error: class, interface, or enum expected
		}
		^
Main.java:108: error: class, interface, or enum expected
			root = update(root);
			^
Main.java:109: error: class, interface, or enum expected
			root = insert(root, new node(a[i]));
			^
Main.java:110: error: class, interface, or enum expected
		}
		^
Main.java:112: error: class, interface, or enum expected
		pair<node*, node*> splitted = split(root, val);
		^
Main.java:113: error: class, interface, or enum expected
		if(splitted.Y != nullptr){
		^
Main.java:115: error: class, interface, or enum expected
		}
		^
Main.java:117: error: class, interface, or enum expected
	}
	^
Main.java:119: error: class, interface, or enum expected
}
^
Main.java:123: error: class, interface, or enum expected
	cin.tie(0);
	^
Main.java:124: error: class, interface, or enum expected
	cout.tie(0);
	^
Main.java:125: error: class, interface, or enum expected
	srand(chrono::system_clock::now().time_since_epoch().count());
	^
Main.java:127: error: class, interface, or enum expected
   	cin >> n >> k;
   	^
Main.java:128: error: class, interface, or enum expected
   	for(int i = 1;i <= n;i++){
   	^
Main.java:128: error: class, interface, or enum expected
   	for(int i = 1;i <= n;i++){
   	              ^
Main.java:128: error: class, interface, or enum expected
   	for(int i = 1;i <= n;i++){
   	                     ^
Main.java:130: error: class, interface, or enum expected
   	}
   	^
Main.java:132: error: class, interface, or enum expected
   	ll tp = 1e14;
   	^
Main.java:133: error: class, interface, or enum expected
   	while(tl <= tr){
   	^
Main.java:135: error: class, interface, or enum expected
   		ll cnt = solve(tm);
   		^
Main.java:137: error: class, interface, or enum expected
   		if(cnt < k){
   		^
Main.java:139: error: class, interface, or enum expected
   		}
   		^
Main.java:142: error: class, interface, or enum expected
   			tp = tm;
   			^
Main.java:143: error: class, interface, or enum expected
   		}
   		^
Main.java:146: error: class, interface, or enum expected
   	return 0;
   	^
Main.java:147: error: class, interface, or enum expected
}
^
87 errors
stdout
copy 
Standard output is empty
https://ideone.com/6kVdIO
language:
Java (HotSpot 12)
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!