fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 1e5 + 5;
  11.  
  12. int cur_node = 0;
  13. struct NODE{
  14. 	ll val = 0;
  15. 	int L,R;
  16. };
  17.  
  18. //sparse segment tree
  19. vector <NODE> seg;
  20. vector <pair<ll,ll>> res;
  21.  
  22. ll sum(ll l,ll r){
  23. 	if (l > r) return 0;
  24. 	return (r - l + 1) * (l + r)/2;
  25. }
  26.  
  27. inline pir getpair (ll n,ll x){
  28. 	ll N = n - 1;
  29.  
  30. 	int u = 1,l = 1,r = n;
  31. 	while (l <= r){
  32. 		int w = (l + r)/2;
  33. 		if (sum(n - w,n - 1) >= x){
  34. 			u = w;
  35. 			r = w - 1;
  36. 		}
  37. 		else l = w + 1;
  38. 	}
  39.  
  40. 	x -= sum(n - (u - 1),n - 1);
  41.  
  42. 	int v = x + u;
  43. 	if (u > v) swap(u,v);
  44. 	return {u,v};
  45. }
  46.  
  47. void init(ll n){
  48. 	ll T = n*(n - 1)/2;
  49. 	seg.push_back({T,0,0});
  50. }
  51. ll walk_on_tree(ll l,ll r,int node,ll t){
  52. 	ll val = seg[node].val;
  53. 	ll w = (l + r)/2;
  54.  
  55. 	if (l == r) return l;
  56.  
  57. 	//if child node is not initialized, that means no deletion operation has reached
  58. 	//initialize new node
  59. 	if (!seg[node].L){
  60. 	   seg[node].L = ++cur_node;
  61.        seg.push_back({w - l + 1,0,0});  
  62. 	}
  63. 	if (!seg[node].R){
  64. 	 	seg[node].R = ++cur_node;
  65. 	 	seg.push_back({r - w,0,0});
  66. 	}
  67. 	//////////
  68. 	if (seg[seg[node].L].val >= t)
  69. 	  return walk_on_tree(l,w,seg[node].L,t);
  70.  
  71. 	t -= seg[seg[node].L].val;
  72. 	return walk_on_tree(w + 1,r,seg[node].R,t);
  73. }
  74. void deletion(ll l,ll r,int node,ll x){
  75. 	ll val = seg[node].val;
  76. 	ll w = (l + r)/2;
  77.  
  78. 	if (l > x || r < x) return;
  79. 	if (l == r){
  80. 		seg[node].val = 0;
  81. 		return;
  82. 	}
  83. 	//if child node is not initialized, that means no deletion operation has reached
  84. 	//initialize new node
  85. 	if (!seg[node].L){
  86. 	   seg[node].L = ++cur_node;
  87.        seg.push_back({w - l + 1,0,0});  
  88. 	}
  89. 	if (!seg[node].R){
  90. 	 	seg[node].R = ++cur_node;
  91. 	 	seg.push_back({r - w,0,0});
  92. 	}
  93. 	//////////
  94.  
  95. 	int L = seg[node].L,R = seg[node].R;
  96.  
  97. 	deletion(l,w,L,x);
  98. 	deletion(w + 1,r,R,x);
  99.  
  100. 	seg[node].val = seg[L].val + seg[R].val;
  101. }
  102.  
  103. int main(){
  104. 	ios_base::sync_with_stdio(false);
  105. 	cin.tie(0);cout.tie(0);
  106. 	//freopen("GENTEST.inp","r",stdin);
  107. 	//freopen("GENTEST.out","w",stdout);
  108. 	ll n;int m;
  109. 	cin >> n >> m;
  110. 	init(n);
  111. 	if (n == 1) return 0;
  112.  
  113. 	ll N = n*(n - 1);
  114. 	vector <ll> lst;
  115. 	while (m--){
  116. 		ll t;
  117. 		cin >> t;
  118.  
  119. 		ll x = walk_on_tree(1,N,0,t);
  120.  
  121. 		deletion(1,N,0,x);
  122.  
  123. 		res.push_back(getpair(n,x));
  124. 	}
  125.  
  126. 	for (pir p : res) cout << p.fi << " " << p.se << "\n";
  127.  
  128. 	return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eKvTvE
language:
C++14 (gcc 8.3)
created:
1 day 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!