fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define MAXN (1 << 20)
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9.  
  10. template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11.  
  12. struct node
  13. {
  14. 	long long cnt;
  15. 	long long left, right, id;
  16.  
  17. 	node() {left = -1, right = -1, id = -1; cnt = 0;}
  18. };
  19.  
  20. node broken;
  21.  
  22. struct dynamic_segment_tree
  23. {
  24. 	long long cnt;
  25. 	node tr[MAXN];
  26.  
  27. 	long long newnode()
  28. 	{	
  29. 		tr[cnt].id = cnt;
  30. 		return cnt++;
  31. 	}
  32.  
  33. 	void expand(long long idx, long long lb, long long rb)
  34. 	{
  35. 		long long mid = (lb + rb) >> 1;
  36.  
  37. 		if(tr[idx].left == -1)
  38. 		{
  39. 			tr[idx].left = newnode();
  40. 			tr[tr[idx].left].cnt = (mid - lb + 1);
  41. 		}
  42.  
  43. 		if(tr[idx].right == -1)
  44. 		{
  45. 			tr[idx].right = newnode();
  46. 			tr[tr[idx].right].cnt = (rb - mid);
  47. 		}
  48. 	}
  49.  
  50. 	void init()
  51. 	{
  52. 		cnt = 0;
  53. 		tr[0].id = newnode();
  54. 	}
  55.  
  56. 	node merge(node l, node r)
  57. 	{
  58. 		node ret;
  59. 		ret.cnt = l.cnt + r.cnt;
  60. 		return ret;
  61. 	}
  62.  
  63. 	void update(long long idx)
  64. 	{
  65. 		tr[idx].cnt = tr[tr[idx].left].cnt + tr[tr[idx].right].cnt;
  66. 	}
  67.  
  68. 	long long query(long long k, long long l, long long r, long long idx)
  69. 	{
  70. 		if(l == r)
  71. 			return l;
  72.  
  73. 		long long mid = (l + r) >> 1;
  74. 		expand(idx, l, r);
  75.  
  76. 		//printf("[%lld, %lld] : %lld,    -->     %lld, %lld\n", l, r, k, tr[tr[idx].left].cnt,
  77. 		//tr[tr[idx].right].cnt);
  78.  
  79. 		if(tr[tr[idx].left].cnt >= k) return query(k, l, mid, tr[idx].left);
  80. 		else return query(k - tr[tr[idx].left].cnt, mid + 1, r, tr[idx].right);	
  81. 	}
  82.  
  83. 	void update(long long pos, long long val, long long l, long long r, long long idx)
  84. 	{
  85. 		if(l > pos || r < pos)
  86. 			return;
  87.  
  88. 		if(l == r && l == pos)
  89. 		{
  90. 			tr[idx].cnt += val;
  91. 			return;
  92. 		}
  93.  
  94. 		long long mid = (l + r) >> 1;
  95. 		expand(idx, l, r);
  96.  
  97. 		//printf("[%lld, %lld] : %lld,    -->     %lld, %lld\n", l, r, idx, tr[tr[idx].left].cnt,
  98. 		//tr[tr[idx].right].cnt);
  99.  
  100. 		update(pos, val, l, mid, tr[idx].left);
  101. 		update(pos, val, mid + 1, r, tr[idx].right);
  102.  
  103. 		update(idx);	
  104. 	}	
  105. };
  106.  
  107. long long N;
  108.  
  109. void read()
  110. {
  111. 	scanf("%lld", &N);
  112. }
  113.  
  114. dynamic_segment_tree t;
  115.  
  116. void solve()
  117. {
  118. 	t.init();
  119.  
  120. 	long long Q;
  121. 	scanf("%lld", &Q);
  122.  
  123. 	while(Q--)
  124. 	{
  125. 		char type[2];
  126. 		long long pos;
  127.  
  128. 		scanf("%s %lld", &type, &pos);
  129.  
  130. 		long long val = t.query(pos, 1, N, 0);
  131.  
  132. 		if(type[0] == 'D')
  133. 			t.update(val, -1, 1, N, 0);
  134. 		else
  135. 			printf("%lld\n", val);
  136. 	}	
  137. }
  138.  
  139. int main()
  140. {
  141. 	read();
  142. 	solve();
  143. 	return 0;
  144. }
  145.  
  146.  
Time limit exceeded #stdin #stdout 5s 36256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PmG5Qb
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!