fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-11-19 09:06:49
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-11-19 13:20:09
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name ""
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)3e5+10;
  54. int n,q;
  55.  
  56. struct Query {
  57. 	int type,a,b,k;
  58. } query[N];
  59.  
  60. namespace sub1 {
  61.  
  62. 	bool approved() {
  63. 		return n <= 100 and q <= 100;
  64. 	}
  65.  
  66. 	void solve(void)
  67. 	{
  68. 		multiset<int> st;
  69. 		FOR(i,1,n) st.insert(1);
  70. 		FOR(rep,1,q)
  71. 			if (query[rep].type == 1)
  72. 			{
  73. 				int a = query[rep].a, b = query[rep].b;
  74. 				if (st.find(a) != st.end())
  75. 					st.erase(st.find(a));
  76. 				if (st.find(b) != st.end())
  77. 					st.erase(st.find(b));
  78. 				st.insert(a+b);
  79. 			}
  80. 			else 
  81. 			{
  82. 				int k = query[rep].k;
  83. 				vi vec;
  84. 				for (auto it = st.begin(); it != st.end(); it++)
  85. 					for (auto it2 = next(it); it2 != st.end(); it2++) 
  86. 						vec.pb(abs(*it-*it2));
  87. 				sort(all(vec));
  88. 				cout << vec[k-1] << endl;
  89. 			}
  90. 	}
  91.  
  92. }
  93.  
  94. namespace sub4 {
  95.  
  96. 	int L[N],R[N],ans[N];
  97. 	vi mem[N];
  98.  
  99. 	bool approved() {
  100. 		int start = 0, last = 0;
  101. 		FOR(i,1,q)
  102. 			if (query[i].type == 1) last = i;
  103. 			else 
  104. 			{
  105. 				if (!start)
  106. 					start = i;
  107. 			}
  108. 		return (last < start);
  109. 	}
  110.  
  111. 	int count(vi &vec, int mid)
  112. 	{
  113. 		int n = sz(vec), cnt = 0, j = 0;
  114. 		FOR(i,0,n-1)
  115. 		{
  116. 			if (j < i+1) j = i+1;
  117. 			while (j < n and vec[j]-vec[i] <= mid) j++;
  118. 			cnt += j-i-1;
  119. 		}
  120. 		return cnt;
  121. 	}
  122.  
  123. 	void solve(void)
  124. 	{
  125. 		multiset<int> st;
  126. 		FOR(i,1,n) st.insert(1);
  127. 		int last;
  128. 		FOR(rep,1,q)
  129. 			if (query[rep].type == 1)
  130. 			{
  131. 				int a = query[rep].a, b = query[rep].b;
  132. 				if (st.find(a) != st.end())
  133. 					st.erase(st.find(a));
  134. 				if (st.find(b) != st.end())
  135. 					st.erase(st.find(b));
  136. 				st.insert(a+b);
  137. 				last = rep;
  138. 			}
  139. 		vi vec, K;
  140. 		for (int x : st) vec.pb(x);
  141. 		FOR(i,last+1,q)
  142. 			if (query[i].type == 2) 
  143. 			{
  144. 				int k = query[i].k;
  145. 				K.pb(k);
  146. 			}
  147. 		int mx = vec.back()-vec.front(), len = sz(K);
  148. 		FOR(i,0,len-1) L[i] = 0, R[i] = mx;
  149. 		while (true)
  150. 		{
  151. 			bool check = false;
  152. 			FOR(i,0,len-1)
  153. 				if (L[i] <= R[i])
  154. 				{
  155. 					int mid = (L[i]+R[i])>>1;
  156. 					mem[mid].pb(i);
  157. 					check = true;
  158. 				}
  159. 			if (!check) break;
  160. 			FOR(d,0,mx)
  161. 			{
  162. 				if (mem[d].empty()) continue;
  163. 				int cnt = count(vec,d);
  164. 				for (int id : mem[d])
  165. 					if (cnt >= K[id]) ans[id] = d, R[id] = d-1;
  166. 					else L[id] = d+1; 
  167. 			}
  168. 			FOR(d,0,mx) mem[d].clear();
  169. 		}
  170. 		FOR(i,0,sz(K)-1) cout << ans[i] << endl;
  171. 	}
  172.  
  173. }
  174.  
  175. namespace sub5 {
  176.  
  177. 	bool approved() {
  178. 		return n <= 5e4 and q <= 5e4;
  179. 	}
  180.  
  181. 	bool check(vi &a, int mid, int k)
  182. 	{
  183. 		int n = sz(a), cnt = 0, j = 0;
  184. 		FOR(i,0,n-1)
  185. 		{
  186. 			if (j < i+1) j = i+1;
  187. 			while (j < n and a[j]-a[i] <= mid) j++;
  188. 			cnt += (j-i-1);
  189. 		}
  190. 		return (cnt >= k);
  191. 	}
  192.  
  193. 	void solve(void)
  194. 	{
  195. 		vi vec;
  196. 		FOR(i,1,n) vec.pb(1);
  197. 		FOR(rep,1,q)
  198. 			if (query[rep].type == 1)
  199. 			{
  200. 				int a = query[rep].a, b = query[rep].b;
  201. 				auto it = lower_bound(all(vec),a);
  202. 				if (it != vec.end()) vec.erase(it);
  203. 				auto it2 = lower_bound(all(vec),b);
  204. 				if (it2 != vec.end()) vec.erase(it2);
  205. 				int x = a+b;
  206. 				auto it3 = lower_bound(all(vec),x);
  207. 				if (it3 == vec.end()) vec.pb(x);
  208. 				else vec.insert(it3,x);
  209. 			}
  210. 			else
  211. 			{
  212. 				int k = query[rep].k;
  213. 				int l = 0, r = vec.back()-vec.front(), ans = 0;
  214. 				while (l <= r)
  215. 				{
  216. 					int mid = (l+r)>>1;
  217. 					if (check(vec,mid,k)) ans = mid, r = mid-1;
  218. 					else l = mid+1;
  219. 				}
  220. 				cout << ans << endl;
  221. 			}
  222. 	}
  223.  
  224. }
  225.  
  226. namespace sub6 {
  227.  
  228. 	int pre[N];
  229.  
  230. 	bool check(vii &vec, int mid, int k)
  231. 	{
  232. 		int n = sz(vec), j = 0, res = 0;
  233. 		FOR(i,0,n-1)
  234. 		{
  235. 			if (j < i+1) j = i+1;
  236. 			while (j < n and vec[j].fi-vec[i].fi <= mid) j++;
  237. 			if (j-1 >= i+1)
  238. 				res += vec[i].se*(pre[j-1]-pre[i]);
  239. 		}
  240. 		return (res >= k);
  241. 	}
  242.  
  243. 	void solve(void)
  244. 	{
  245. 		unordered_map<int,int> mp;
  246. 		mp[1] = n;
  247. 		FOR(rep,1,q)
  248. 			if (query[rep].type == 1)
  249. 			{
  250. 				int a = query[rep].a, b = query[rep].b;
  251. 				auto it1 = mp.find(a);
  252. 				if (!(it1 == mp.end() or !it1->se))
  253. 				{
  254. 					it1->se--;
  255. 					if (!it1->se) mp.erase(it1);
  256. 				}
  257. 				auto it2 = mp.find(b);
  258. 				if (!(it2 == mp.end() or !it2->se))
  259. 				{
  260. 					it2->se--;
  261. 					if (!it2->se) mp.erase(it2);
  262. 				}
  263. 				int val = a+b;
  264. 				mp[val]++;
  265. 			}
  266. 			else
  267. 			{
  268. 				int k = query[rep].k;
  269. 				vii vec;
  270. 				for (auto x : mp)
  271. 					if (x.se) vec.pb(x);
  272. 				sort(all(vec));
  273. 				int m = sz(vec);
  274. 				if (m == 1)
  275. 				{
  276. 					cout << 0 << endl;
  277. 					continue;
  278. 				}
  279. 				int same = 0;
  280. 				for (auto x : mp) same += x.se*(x.se-1)/2;
  281. 				if (k <= same) 
  282. 				{
  283. 					cout << 0 << endl;
  284. 					continue;
  285. 				}
  286. 				k -= same;
  287. 				pre[0] = vec[0].se;
  288. 				FOR(i,1,m-1) pre[i] = pre[i-1]+vec[i].se;
  289. 				int l = 1, r = vec.back().fi-vec.front().fi, ans;
  290. 				while (l <= r)
  291. 				{
  292. 					int mid = (l+r)>>1;
  293. 					if (check(vec,mid,k)) ans = mid, r = mid-1;
  294. 					else l = mid+1;
  295. 				}
  296. 				cout << ans << endl;
  297. 			}
  298. 	}
  299.  
  300. }
  301.  
  302. bool M2;
  303. signed main()
  304. {
  305.     fast;
  306.     if (fopen(name".inp","r"))
  307.     {
  308.     	freopen(name".inp","r",stdin);
  309.     	freopen(name".out","w",stdout);
  310.     }
  311.     cin >> n >> q;
  312.     FOR(i,1,q)
  313.     {
  314.     	cin >> query[i].type;
  315.     	if (query[i].type == 1)
  316.     		cin >> query[i].a >> query[i].b;
  317.     	else cin >> query[i].k;
  318.     }
  319.     // if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  320.     // if (sub4::approved()) return sub4::solve(), time(), memory(), 0;
  321.     if (sub5::approved()) return sub5::solve(), time(), memory(), 0;
  322.     sub6::solve();
  323.     time();
  324.     memory();
  325.     return 0;
  326. }
  327. // ██░ ██  █    ██  ███▄    █   ▄████
  328. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  329. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  330. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  331. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  332. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  333. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  334. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  335. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 12092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:8.602ms.
25.178 MB
https://ideone.com/pyxKZW
language:
C++14 (gcc 8.3)
created:
4 hours 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!