{"id":399808,"date":"2024-06-29T14:53:37","date_gmt":"2024-06-29T14:53:37","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=399808"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=399808","title":{"rendered":"<span>\u041a\u0430\u043a \u044f \u043f\u0438\u0441\u0430\u043b \u0411\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0443\u044e \u043a\u0443\u0447\u0443<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h3>\u041e\u0433\u043b\u0430\u0432\u043b\u0435\u043d\u0438\u0435<\/h3>\n<ul>\n<li>\n<p>\u041a\u0430\u043a \u044f \u043d\u0430\u0447\u0430\u043b \u044d\u0442\u0443 \u0437\u0430\u0442\u0435\u044e<\/p>\n<\/li>\n<li>\n<p>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430?<\/p>\n<\/li>\n<li>\n<p>\u041a\u0430\u043a \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0441\u0432\u043e\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/p>\n<\/li>\n<li>\n<p>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e map \u0432 c++<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043c\u043e\u043c<\/p>\n<\/li>\n<li>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0438<\/p>\n<\/li>\n<li>\n<p>\u041d\u043e\u0432\u044b\u0435 \u0442\u0435\u0441\u0442\u044b<\/p>\n<\/li>\n<li>\n<p>\u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e \u0442\u0435\u0441\u0442\u0430\u043c \u0432 \u0438\u0442\u043e\u0433\u0435: \u0440\u0435\u0430\u043b\u044c\u043d\u0430\u044f \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u043f\u0430\u043c\u044f\u0442\u044c<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0447\u0451\u043c \u0436\u0435 \u043f\u043b\u043e\u0445\u043e \u043c\u043e\u0451 \u0440\u0435\u0448\u0435\u043d\u0438\u0435? \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0436\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0432\u0441\u0435 \u0434\u0435\u043b\u0430<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0436\u0435\u043b\u0430\u043d\u0438\u044f \u043e\u0442 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439<\/p>\n<\/li>\n<\/ul>\n<h3>\u041a\u0430\u043a \u044f \u043d\u0430\u0447\u0430\u043b \u044d\u0442\u0443 \u0437\u0430\u0442\u0435\u044e<\/h3>\n<p>\u042f \u0441\u0435\u0439\u0447\u0430\u0441 \u0438\u0437\u0443\u0447\u0430\u044e \u043f\u0440\u043e\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0432 \u043e\u0434\u0438\u043d \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u044b\u0439 \u0432\u0435\u0447\u0435\u0440 \u044f \u0440\u0435\u0448\u0438\u043b \u0441\u043e\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043a \u0441\u0435\u0431\u0435 \u043d\u0430 <a href=\"https:\/\/github.com\/mdan2000\/algorithms-and-data-structures\" rel=\"noopener noreferrer nofollow\">\u0433\u0438\u0442\u0445\u0430\u0431 <\/a>(\u0438 \u0434\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u044d\u0442\u043e \u0434\u0435\u043b\u0430\u044e). \u0417\u0430\u0445\u043e\u0442\u0435\u043b \u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0451 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u044b\u043c, \u0435\u0441\u043b\u0438 \u0447\u0442\u043e-\u0442\u043e \u043c\u043d\u0435 \u0440\u0435\u0437\u043a\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f, \u0442\u043e \u044f \u0441\u043c\u043e\u0433 \u0437\u0430 \u0441\u0447\u0438\u0442\u0430\u043d\u043d\u044b\u0435 \u0441\u0435\u043a\u0443\u043d\u0434\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0431\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438\u043b\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c. \u0417\u0432\u0443\u0447\u0438\u0442 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043d\u0430 \u043a\u043e\u043d\u0442\u0435\u0441\u0442\u044b \u0441 <a href=\"https:\/\/codeforces.com\/\" rel=\"noopener noreferrer nofollow\">codeforces<\/a>.<\/p>\n<p>\u042f \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0441\u044f \u0441 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430\u043c\u0438 \u0438 \u0440\u0435\u0448\u0438\u043b \u0437\u0434\u0435\u0441\u044c \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u043e\u043f\u044b\u0442\u043e\u043c \u0441 \u0442\u0435\u043c, \u043a\u0442\u043e \u0442\u0430\u043a\u0436\u0435, \u043a\u0430\u043a \u0438 \u044f, \u043c\u0430\u043b\u043e \u0437\u043d\u0430\u043a\u043e\u043c \u0441 \u043f\u0440\u043e\u043c. \u043f\u0440\u043e\u0433\u043e\u0439 \u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u0443\u0432\u043b\u0435\u043a\u0430\u043b\u0441\u044f \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u043d\u044b\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c.<\/p>\n<h3>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430?<\/h3>\n<p>\u041e\u0431 \u044d\u0442\u043e\u043c \u0443\u0436\u0435 \u043d\u0438 \u0440\u0430\u0437 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u043b\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043d\u0430 \u0441\u0430\u0439\u0442\u0435 <a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0418\u0422\u041c\u041e<\/a>, <a href=\"https:\/\/habr.com\/ru\/post\/135232\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a> \u0438 \u0435\u0449\u0451 \u0432 \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u044b\u0445 <a href=\"https:\/\/www.youtube.com\/watch?v=CeAjTL-Fshs\" rel=\"noopener noreferrer nofollow\">\u043b\u0435\u043a\u0446\u0438\u044f\u0445<\/a> \u043e\u0442 \u041c\u0430\u0432\u0440\u0438\u043d\u0430 \u041f\u0430\u0432\u043b\u0430 \u042e\u0440\u044c\u0435\u0432\u0438\u0447\u0430 (\u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0435\u0433\u043e \u0432\u0438\u0434\u0435\u043e, \u043e\u043d\u043e \u043e\u0447\u0435\u043d\u044c \u043a\u0440\u0443\u0442\u043e\u0435!).<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043e\u0442\u043a\u043e, \u0442\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430 &#8212; \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c.<\/p>\n<p>\u0412 \u043a\u0443\u0447\u0435, \u0433\u0434\u0435 \u0443 \u043d\u0430\u0441<img decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6f8\/c69\/707\/6f8c69707ed34ec4c2fbf25db247b7ad.svg\"\/>\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/p>\n<ul>\n<li>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u043a\u0443\u0447\u0443 \u0437\u0430<img decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b5e\/bea\/230\/b5ebea2306351d084f1a15073ab0c684.svg\"\/>(\u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f)<\/p>\n<\/li>\n<li>\n<p>\u0412\u0437\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u0437\u0430<img decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/525\/728\/96b\/52572896be08f8e1d5bc703ef08a61a0.svg\"\/>(\u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438, \u0432 \u043c\u043e\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u044d\u0442\u043e \u0442\u0430\u043a)<\/p>\n<\/li>\n<li>\n<p>\u0418\u0437\u044a\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u0437\u0430<img decoding=\"async\" class=\"formula inline\" source=\"O\\log(n)\" alt=\"O\\log(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/308\/5d1\/0ba\/3085d10ba8d49dcacbef677a834f2d4f.svg\"\/><\/p>\n<\/li>\n<\/ul>\n<p>\u0418 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0435\u0441\u0442\u044c \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e, \u0435\u0441\u043b\u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0441 \u043e\u0431\u044b\u0447\u043d\u043e\u0439 \u043a\u0443\u0447\u0435\u0439! \u0412 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c merge \u0434\u0432\u0443\u0445 \u043a\u0443\u0447 \u0437\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log n)\" alt=\"O(\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/936\/173\/1d7\/9361731d77bb69c303369ee624223a90.svg\"\/>. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u043e \u00a0\u00af\\_(\u30c4)_\/\u00af<\/p>\n<h3>\u041a\u0430\u043a \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0441\u0432\u043e\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/h3>\n<p>\u0417\u0434\u0435\u0441\u044c \u043f\u043e\u043c\u043e\u0433 <a href=\"https:\/\/codeforces.com\/\" rel=\"noopener noreferrer nofollow\">codeforces<\/a> \u0441 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 <a href=\"https:\/\/polygon.codeforces.com\/\" rel=\"noopener noreferrer nofollow\">polygon<\/a>. \u0417\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a8d\/3f8\/c6a\/a8d3f8c6a40f7f07972b1898204fb9e9.PNG\" alt=\"\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438\" title=\"\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438\" width=\"888\" height=\"472\"\/><figcaption>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fb1\/850\/9da\/fb18509da66aad3dd7fc9a5e838ef41a.PNG\" alt=\"\u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430\" title=\"\u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430\" width=\"877\" height=\"469\"\/><figcaption>\u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430<\/figcaption><\/figure>\n<p>\u0421\u0434\u0435\u043b\u0430\u043d\u044b \u044d\u0442\u0438 &#171;\u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u044b&#187; \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0442\u0435\u0441\u0442\u044b \u0431\u044b\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0438 \u0435\u0441\u043b\u0438 \u0431\u044b\u043b\u0430 \u043a\u0430\u043a\u0430\u044f-\u0442\u043e \u0431\u0430\u0433\u0430, \u0442\u043e \u043e\u043d\u0430 \u0432\u044b\u044f\u0441\u043d\u0438\u043b\u0430\u0441\u044c. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0442\u0435\u0441\u0442\u043e\u0432 \u0431\u044b\u043b\u043e 14 (\u0438 \u0432 \u0442\u0435\u0447\u0435\u043d\u0438\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f).<\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e map \u0432 c++<\/h3>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\">#include &lt;iostream> #include &lt;map> #include &lt;string>   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int t; cin >> t;     while(t--) {         map&lt;int, int> heap;         int n; cin >> n;         for (int i = 0; i &lt; n; ++i) {             string op;             cin >> op;             if (op == \"Insert\") {                 int x;                 cin >> x;                 heap[x]++;             } else if (op == \"GetMin\") {                 cout &lt;&lt; heap.begin()->first &lt;&lt; '\\n';             } else if (op == \"EraseMin\") {                 heap.begin()->second--;                 if (heap.begin()->second == 0) {                     heap.erase(heap.begin());                 }             }         }     }     return 0; }<\/code><\/pre>\n<p>\u041f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u0432\u043e\u0434\u0438\u0442\u0441\u044f <code>map&lt;int, int><\/code> , \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0432\u0435\u0434\u0451\u0442\u0441\u044f \u043f\u043e\u0434\u0441\u0447\u0451\u0442 \u043a\u043e\u043b-\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e <code>map<\/code> \u0445\u0440\u0430\u043d\u0438\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0442\u0430\u043a, \u0447\u0442\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430 \u043e\u0442 begin \u0434\u043e end \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u044f \u043a\u043b\u044e\u0447\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0437\u0430<img decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d27\/705\/085\/d27705085622f50a64de45dd191d9032.svg\"\/>, \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0437\u0430<img decoding=\"async\" class=\"formula inline\" source=\"O(\\log(n))\" alt=\"O(\\log(n))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a0e\/84d\/b07\/a0e84db0748946def89346ac5b879526.svg\"\/>. \u0415\u0441\u043b\u0438 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0435\u043f\u0435\u0440\u044c<img decoding=\"async\" class=\"formula inline\" source=\"0\" alt=\"0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/80a\/97f\/1da\/80a97f1da8b222e1a4ac6ed5e1aed82d.svg\"\/>\u0440\u0430\u0437, \u0442\u043e \u043e\u043d \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0437 <code>map<\/code> , \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u0438 \u043d\u0435 \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438.<\/p>\n<p>\u041f\u0440\u043e\u0448\u0443 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0442\u0443\u0442 \u043d\u0435 \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 <code>set<\/code>, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044b (\u043f\u0440\u043e <code>multiset<\/code> \u0430\u0432\u0442\u043e\u0440 \u0440\u0435\u0448\u0438\u043b \u0442\u0430\u043a\u0442\u0438\u0447\u043d\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u0442\u044c).<\/p>\n<h3>\u041f\u0435\u0440\u0432\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043c\u043e\u043c<\/h3>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0430\u0432\u0430\u043b\u0430 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0443 \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b\u0430 \u0442\u0430\u043a:<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u043c\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"cpp\">#include &lt;memory> #include &lt;cassert> #include &lt;functional> #include &lt;iostream> #include &lt;algorithm> #include &lt;list> #include &lt;stdexcept>   template&lt;typename T> class BinHeap { private: struct BinHeapNode { T key; std::list&lt;std::shared_ptr&lt;BinHeapNode>> childs; size_t degree = 0; };   std::shared_ptr&lt;BinHeapNode> MergeEqualHeap(std::shared_ptr&lt;BinHeapNode> l, std::shared_ptr&lt;BinHeapNode> r) const { if (!cmp(l->key, r->key)) { swap(l, r); } l->childs.insert(l->childs.end(), r); l->degree++; return l; }   public: BinHeap() : size_(0) {};   BinHeap(const std::function&lt;bool(T, T)>&amp; cmpFunc) : size_(0), cmp(cmpFunc) {};   BinHeap(std::list&lt;std::shared_ptr&lt;BinHeapNode>>&amp; newChilds, const std::function&lt;bool(T, T)>&amp; cmpFunc) : cmp(cmpFunc) { Heap_ = newChilds; size_t newSize_ = 0; for (const auto&amp; c : Heap_) { newSize_ += (1u &lt;&lt; c->degree); } size_ = newSize_; }   void push(const T&amp; newKey) { std::shared_ptr&lt;BinHeapNode> node = std::make_shared&lt;BinHeapNode>(); node->key = newKey; auto it = Heap_.begin(); while (it != Heap_.end() &amp;&amp; (*it)->degree == node->degree) { if (cmp((*it)->key, node->key)) { (*it)->childs.insert((*it)->childs.end(), node); (*it)->degree++; node = *it; it = Heap_.erase(it); } else { node->childs.insert(node->childs.end(), *it); node->degree++; } } Heap_.insert(it, node); ++size_; }   void Merge(BinHeap&amp; r) { auto l = *this; auto itl = l.Heap_.begin(); auto itr = r.Heap_.begin(); std::list&lt;std::shared_ptr&lt;BinHeapNode>> newHeap; while (itl != l.Heap_.end() &amp;&amp; itr != r.Heap_.end()) { if ((*itl)->degree == (*itr)->degree) { newHeap.insert(newHeap.end(), MergeEqualHeap(*itl, *itr)); itl = l.Heap_.erase(itl); itr = r.Heap_.erase(itr); } else if (!newHeap.empty() &amp;&amp; (*itl)->degree == newHeap.back()->degree) { auto node = newHeap.back(); newHeap.pop_back(); newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itl)); itl = l.Heap_.erase(itl); } else if (!newHeap.empty() &amp;&amp; (*itr)->degree == newHeap.back()->degree) { auto node = newHeap.back(); newHeap.pop_back(); newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itr)); itr = r.Heap_.erase(itr); } else { if (cmp((*itl)->key, (*itr)->key)) { newHeap.insert(newHeap.end(), *itl); itl = l.Heap_.erase(itl); } else { newHeap.insert(newHeap.end(), *itr); itr = r.Heap_.erase(itr); } } }   while (itl != l.Heap_.end()) { newHeap.insert(newHeap.end(), *itl); itl = l.Heap_.erase(itl); }   while (itr != r.Heap_.end()) { newHeap.insert(newHeap.end(), *itr); itr = r.Heap_.erase(itr); } Heap_ = newHeap; }   size_t size() const { return size_; }   T top() const { if (Heap_.empty()) { return {}; \/\/ throw??? } T res = Heap_.front()->key; for (const auto&amp; node : Heap_) { if (cmp(node->key, res)) { res = node->key; } } return res; }   void pop() { if (Heap_.empty()) { throw std::runtime_error(\"Erase from empty BinHeap\"); } auto minEl = Heap_.begin(); for (auto it = Heap_.begin(); it != Heap_.end(); ++it) { if (cmp((*it)->key, (*minEl)->key)) { minEl = it; } } BinHeap&lt;T> newHeap((*minEl)->childs, cmp); Heap_.erase(minEl); this->Merge(newHeap); }   private: size_t size_; std::list&lt;std::shared_ptr&lt;BinHeapNode>> Heap_; std::function&lt;bool(T, T)> cmp = [](const T&amp; l, const T&amp; r) { return l &lt; r; }; };   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int t; cin >> t;     while(t--) {         BinHeap&lt;int> heap;         int n; cin >> n;         for (int i = 0; i &lt; n; ++i) {             string op;             cin >> op;             if (op == \"Insert\") {                 int x;                 cin >> x;                 heap.push(x);             } else if (op == \"GetMin\") {                 cout &lt;&lt; heap.top() &lt;&lt; endl;             } else if (op == \"EraseMin\") {                 heap.pop();             }         }     }     return 0; }<\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u042d\u0442\u043e \u0434\u0430\u0432\u0430\u043b\u043e ML (Memory Limit) \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0442\u0435\u0441\u0442\u0435. \u041f\u0440\u043e\u0442\u0435\u0447\u043a\u0430 \u0431\u044b\u043b\u0430 \u0437\u043d\u0430\u0442\u043d\u0430\u044f \u0438 \u043c\u043e\u0435\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u043e\u0439 \u043e\u0442 \u043d\u0435\u0451 \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043a\u0443\u0447\u0438, \u043f\u043e\u043a\u0430 \u043e\u043d\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430\u044f. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u043c\u0435\u0442\u043e\u0434 <code>empty()<\/code> (\u043d\u0430\u0434\u0435\u044e\u0441\u044c \u0432\u0441\u0435 \u0434\u043e\u0433\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u043e\u043d \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b) \u0438 \u044f \u0434\u0435\u043b\u0430\u043b <code>pop()<\/code> \u0434\u043e \u0442\u043e\u0433\u043e \u043c\u043e\u043c\u0435\u043d\u0442\u0430, \u043f\u043e\u043a\u0430 \u043a\u0443\u0447\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430\u044f \u043f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0441 \u043d\u0435\u0439 \u0440\u0430\u0431\u043e\u0442\u0443.<\/p>\n<p>\u0417\u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u043e? \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0431\u044b\u043b\u043e \u0432\u0441\u0451 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e: \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 map \u0437\u0430\u0445\u043e\u0434\u0438\u043b\u043e \u0437\u0430 498ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 842ms. \u041d\u043e \u0441\u0430\u043c\u044b\u0439 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0442\u0435\u0441\u0442 \u0431\u044b\u043b \u0442\u0430\u043a\u043e\u0432, \u0447\u0442\u043e \u0431\u044b\u043b<img decoding=\"async\" class=\"formula inline\" source=\"10^3\" alt=\"10^3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fdf\/8f0\/14a\/fdf8f014ab6e8de1638635aa670a8d56.svg\"\/>\u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u043e\u0432 <img decoding=\"async\" class=\"formula inline\" source=\"10^3\" alt=\"10^3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/40a\/1cc\/a29\/40a1cca299575290986d10b0e79e0d72.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u0435. \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043c\u043e\u0439 \u0441\u043e\u0441\u0435\u0434, \u0413\u0435\u043e\u0440\u0433\u0438\u0439 \u0428\u0443\u043a\u0430\u043b\u043e\u0432, \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043c\u043d\u0435<\/p>\n<blockquote>\n<p>\u0414\u0430\u043d\u044f, \u0442\u0430\u043a \u044d\u0442\u043e \u0436\u0435 \u0444\u0438\u0433\u043d\u044f, \u0434\u0430\u0432\u0430\u0439 \u043e\u0434\u0438\u043d \u0442\u0435\u0441\u0442 \u043d\u0430<img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/add\/9c0\/a64\/add9c0a648ff5db96498e2cb79a65de6.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439<\/p>\n<\/blockquote>\n<p>\u042f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u044d\u0442\u043e\u0442 \u0442\u0435\u0441\u0442 (15-\u0439 \u0442\u0435\u0441\u0442). \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e<img decoding=\"async\" class=\"formula inline\" source=\"n \\cdot t \\leq 10^6\" alt=\"n \\cdot t \\leq 10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/092\/3bb\/f64\/0923bbf64d5452af446e5a7ab5cdffac.svg\"\/>. \u0412 \u0442\u0435\u043e\u0440\u0438\u0438, \u0432\u0441\u0451 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u043e\u0434\u0438\u043d \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442 \u043d\u0430<img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fa8\/561\/240\/fa85612406ea5f7f66e27e89d8372380.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, map \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043b \u0437\u0430 1045ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0441\u0442\u0430\u043b\u0430 \u0432\u044b\u0434\u0430\u0432\u0430\u0442\u044c TL (Time Limit) \u043d\u0430 15-\u043c \u0442\u0435\u0441\u0442\u0435 (\u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u043d\u0430 \u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442 \u0442\u0435\u0441\u0442, \u043a\u0430\u043a \u0440\u0430\u0437 \u0432 \u0442\u043e\u043c, \u0433\u0434\u0435 \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f<img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bb6\/0e6\/24f\/bb60e624f6aba3e83b9aea5a765b5210.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439).<\/p>\n<h3>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0438<\/h3>\n<p>\u0412\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b\u0430 \u0442\u0430\u043a<\/p>\n<details class=\"spoiler\">\n<summary>\u0412\u0442\u043e\u0440\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"cpp\">#include &lt;memory> #include &lt;cassert> #include &lt;functional> #include &lt;iostream> #include &lt;algorithm> #include &lt;list> #include &lt;stdexcept> #include &lt;unordered_set> #include &lt;queue>   template&lt;typename T> class BinHeap { private:     struct BinHeapNode {         T key;         std::list&lt;std::shared_ptr&lt;BinHeapNode>> childs;         size_t degree = 0;     };       std::shared_ptr&lt;BinHeapNode> MergeEqualHeap(std::shared_ptr&lt;BinHeapNode> l, std::shared_ptr&lt;BinHeapNode> r) const {         if (!cmp(l->key, r->key)) {             swap(l, r);         }         l->childs.insert(l->childs.end(), r);         l->degree++;         return l;     }   public:     BinHeap() : size_(0) {};       BinHeap(const std::function&lt;bool(T, T)>&amp; cmpFunc) :         size_(0),         cmp(cmpFunc) {};       void push(const T&amp; newKey) {           std::shared_ptr&lt;BinHeapNode> node = std::make_shared&lt;BinHeapNode>();         node->key = newKey;         auto it = Heap_.begin();         while (it != Heap_.end() &amp;&amp; (*it)->degree == node->degree) {             if (cmp((*it)->key, node->key)) {                 (*it)->childs.insert((*it)->childs.end(), node);                 (*it)->degree++;                 node = *it;             }             else {                 node->childs.insert(node->childs.end(), *it);                 node->degree++;             }             if (it == MinNode_) {                 MinNode_ = Heap_.end();             }             it = Heap_.erase(it);         }         if (MinNode_ == Heap_.end() || cmp(node->key, (*MinNode_)->key)) {             MinNode_ = Heap_.insert(it, node);         }         else {             Heap_.insert(it, node);         }         ++size_;     }       void Merge(std::list&lt;std::shared_ptr&lt;BinHeapNode>>&amp; r) {         auto itl = Heap_.begin();         auto itr = r.begin();         typename std::list&lt;std::shared_ptr&lt;BinHeapNode>>::iterator node;         while (itl != Heap_.end() &amp;&amp; itr != r.end()) {             if ((*itl)->degree == (*itr)->degree) {                 Heap_.insert(itl, MergeEqualHeap(*itl, *itr)); \/\/ \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u043f\u0435\u0440\u0451\u0434 itl                 itl = Heap_.erase(itl); \/\/ \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u043b\u0438                 ++itr;             }             else if (itl != Heap_.begin() &amp;&amp; (*itl)->degree == (*prev(itl))->degree) {                 node = prev(itl); \/\/ \u0432\u0435\u0440\u0445 \u043d\u043e\u0432\u043e\u0439 \u043a\u0443\u0447\u0438                 Heap_.insert(node, MergeEqualHeap(*node, *itl)); \/\/ \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u043f\u043e itl                 Heap_.erase(node); \/\/ \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442                 itl = Heap_.erase(itl); \/\/             }             else if (itl != Heap_.begin() &amp;&amp; (*itr)->degree == (*prev(itl))->degree) {                 node = prev(itl);                 Heap_.insert(node, MergeEqualHeap(*node, *itr));                 Heap_.erase(node);                 ++itr;             }             else {                 if (cmp((*itl)->key, (*itr)->key)) {                     ++itl;                 }                 else {                     Heap_.insert(itl, *itr);                     ++itr;                 }             }         }           Heap_.insert(Heap_.end(), itr, r.end());         r.clear();     }       size_t size() const {         return size_;     }       T top() const {         if (Heap_.empty()) {             return {}; \/\/ throw???         }         return (*MinNode_)->key;     }       void pop() {         if (Heap_.empty()) {             throw std::runtime_error(\"Erase from empty BinHeap\");         }         std::shared_ptr&lt;BinHeapNode> mn_ptr = *MinNode_;         Heap_.erase(MinNode_);         this->Merge(mn_ptr->childs);           MinNode_ = Heap_.begin();         for (auto it = Heap_.begin(); it != Heap_.end(); ++it) {             if (cmp((*it)->key, (*MinNode_)->key)) {                 MinNode_ = it;             }         }         size_--;     }       bool empty() const {         return size_ == 0;     }   private:     size_t size_;     std::list&lt;std::shared_ptr&lt;BinHeapNode>> Heap_;     typename std::list&lt;std::shared_ptr&lt;BinHeapNode>>::iterator MinNode_ = Heap_.end();     std::function&lt;bool(T, T)> cmp = [](const T&amp; l, const T&amp; r) {         return l &lt; r;     }; };   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int t; cin >> t;     \/\/BinHeap&lt;int> heap;     while (t--) {         BinHeap&lt;int> heap;         int n; cin >> n;         for (int i = 0; i &lt; n; ++i) {             string op;             cin >> op;             if (op == \"Insert\") {                 int x;                 cin >> x;                 heap.push(x);             }             else if (op == \"GetMin\") {                 cout &lt;&lt; heap.top() &lt;&lt; '\\n';             }             else if (op == \"EraseMin\") {                 heap.pop();             }         }         \/\/while (!heap.empty()) {         \/\/    heap.Erase();         \/\/}     }       return 0; }<\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e, \u0437\u0434\u0435\u0441\u044c \u0443\u0436\u0435 \u043d\u0435 \u043d\u0430\u0434\u043e \u0432\u0440\u0443\u0447\u043d\u0443\u044e \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043a\u0443\u0447\u0438, \u0432\u0441\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e. \u0422\u0430\u043a\u0436\u0435 \u0431\u044b\u043b\u0438 \u0443\u0431\u0440\u0430\u043d\u044b \u043b\u0438\u0448\u043d\u0438\u0435 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0435\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043a\u0443\u0447\u0443 \u0438\u0437 <code>list&lt;shared_ptr&lt;BinHeapNode>><\/code>. \u0411\u044b\u043b\u0438 \u043f\u0440\u0438\u043d\u044f\u0442\u044b \u0438\u043d\u044b\u0435 \u043f\u043e\u043f\u044b\u0442\u043a\u0438 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043a\u0443\u0447\u0443, \u043d\u043e \u043e\u043d\u0438 \u043d\u0435 \u0434\u0430\u043b\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432.<\/p>\n<h3>\u041d\u043e\u0432\u044b\u0435 \u0442\u0435\u0441\u0442\u044b<\/h3>\n<p>\u041e\u043f\u044f\u0442\u044c \u0436\u0435, \u043c\u043e\u0439 \u0441\u043e\u0441\u0435\u0434 \u0441\u043a\u0430\u0437\u0430\u043b<\/p>\n<blockquote>\n<p>\u0422\u0430\u043a \u0442\u044b \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439, \u0447\u0442\u043e\u0431\u044b \u0443 \u0442\u0435\u0431\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043a\u0443\u0447\u0435 \u043f\u043e\u0431\u043e\u043b\u044c\u0448\u0435 \u0431\u044b\u043b\u043e, \u0433\u043b\u044f\u0434\u0438\u0448\u044c <code>BinHeap<\/code> \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0437\u0430 \u0441\u0447\u0451\u0442 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e <code>push<\/code> \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e<\/p>\n<\/blockquote>\n<p>\u042f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u0434\u0432\u0430 \u0442\u0435\u0441\u0442\u0430: \u0432 \u043e\u0434\u043d\u043e\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u043f\u043e\u0438\u0441\u043a\u0430 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0431\u044b\u043b\u0438 \u0432 \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u0438 3:3:2 (16-\u0439 \u0442\u0435\u0441\u0442), \u0430 \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u043f\u043e\u043c\u0438\u043c\u043e \u044d\u0442\u043e\u0433\u043e, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c\u0441\u044f \u043d\u0438\u0436\u0435<img decoding=\"async\" class=\"formula inline\" source=\"10^5\" alt=\"10^5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d8b\/1bc\/51f\/d8b1bc51f9720a38f0dd99b13ebea77e.svg\"\/>(17-\u0439 \u0442\u0435\u0441\u0442). \u041f\u043e\u043b\u0443\u0447\u0438\u043b\u0438\u0441\u044c \u0442\u0430\u043a\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b:<\/p>\n<ul>\n<li>\n<p>\u0414\u043b\u044f 16-\u0433\u043e \u0442\u0435\u0441\u0442\u0430 <code>map<\/code> \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0437\u0430 347ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 810ms<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f 17-\u0433\u043e \u0442\u0435\u0441\u0442\u0430 <code>map<\/code> \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0437\u0430 498ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 \u0432\u044b\u0448\u043b\u0430 \u0437\u0430 TL.<\/p>\n<\/li>\n<\/ul>\n<h3>\u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e \u0442\u0435\u0441\u0442\u0430\u043c \u0432 \u0438\u0442\u043e\u0433\u0435: \u0440\u0435\u0430\u043b\u044c\u043d\u0430\u044f \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u043f\u0430\u043c\u044f\u0442\u044c<\/h3>\n<p>\u041d\u0430\u043f\u043e\u043c\u043d\u0438\u043c, \u0447\u0442\u043e \u0431\u044b\u043b\u043e \u043f\u043e \u0442\u0435\u0441\u0442\u0430\u043c:<\/p>\n<ul>\n<li>\n<p>\u0414\u043e 14-\u0433\u043e \u0442\u0435\u0441\u0442\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"10^3\" alt=\"10^3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c21\/be1\/d9c\/c21be1d9c0b953798906bac1eb99d00f.svg\"\/>\u0442\u0435\u0441\u0442\u043e\u0432 \u043f\u043e<img decoding=\"async\" class=\"formula inline\" source=\"10^3\" alt=\"10^3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7ad\/5c4\/ecb\/7ad5c4ecb72aeb57a6608b200a1802de.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u0431\u044b\u043b\u043e \u0432\u0441\u0451 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e, \u0447\u0442\u043e \u0432 <code>map<\/code>, \u0447\u0442\u043e \u0432 \u043c\u043e\u0435\u0439 \u043a\u0443\u0447\u0435 (\u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u0438 \u0432 \u0432\u0438\u0434\u0435 30-50ms \u0438 100-200\u041a\u0411 \u043f\u0430\u043c\u044f\u0442\u0438)<\/p>\n<\/li>\n<li>\n<p>15-\u0439 \u0442\u0435\u0441\u0442<img decoding=\"async\" class=\"formula inline\" source=\"1\" alt=\"1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0a9\/013\/694\/0a90136946683e0a7a83af10ed2423c1.svg\"\/>\u0442\u0435\u0441\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e8e\/9ac\/4de\/e8e9ac4de754a0682ee940a5554cd6b1.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0412\u0441\u0442\u0430\u0432\u043a\u0430\/\u0412\u0437\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\/\u0418\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 2:1:1. \u041f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <code>map<\/code> \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0437\u0430 436ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 1450ms. \u041f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 map \u0441\u044a\u0435\u043b 16k \u041a\u0411, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 32k \u041a\u0411.<\/p>\n<\/li>\n<li>\n<p>16-\u0439 \u0442\u0435\u0441\u0442<img decoding=\"async\" class=\"formula inline\" source=\"1\" alt=\"1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0a9\/013\/694\/0a90136946683e0a7a83af10ed2423c1.svg\"\/>\u0442\u0435\u0441\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e8e\/9ac\/4de\/e8e9ac4de754a0682ee940a5554cd6b1.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0412\u0441\u0442\u0430\u0432\u043a\u0430\/\u0412\u0437\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\/\u0418\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 3:3:2. \u041f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <code>map<\/code> \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0437\u0430 347ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 810ms. \u041f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 map \u0441\u044a\u0435\u043b 10k \u041a\u0411, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 18k \u041a\u0411.<\/p>\n<\/li>\n<li>\n<p>16-\u0439 \u0442\u0435\u0441\u0442<img decoding=\"async\" class=\"formula inline\" source=\"1\" alt=\"1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0a9\/013\/694\/0a90136946683e0a7a83af10ed2423c1.svg\"\/>\u0442\u0435\u0441\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"10^6\" alt=\"10^6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e8e\/9ac\/4de\/e8e9ac4de754a0682ee940a5554cd6b1.svg\"\/>\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0412\u0441\u0442\u0430\u0432\u043a\u0430\/\u0412\u0437\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\/\u0418\u0437\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 3:3:2 \u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043a\u0443\u0447<img decoding=\"async\" class=\"formula inline\" source=\"10^5\" alt=\"10^5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6e5\/4d0\/578\/6e54d05780d6ec2af63f0dfc3bb90cfa.svg\"\/>. \u041f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 <code>map<\/code> \u043e\u0442\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0437\u0430 498ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0430 TL > 2000ms, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u0441\u043c\u044b\u0441\u043b\u0430 \u043d\u0435\u0442.<\/p>\n<\/li>\n<\/ul>\n<h3>\u0412 \u0447\u0451\u043c \u0436\u0435 \u043f\u043b\u043e\u0445\u043e \u043c\u043e\u0451 \u0440\u0435\u0448\u0435\u043d\u0438\u0435? \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0436\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0432\u0441\u0435 \u0434\u0435\u043b\u0430<\/h3>\n<p>\u0414\u0430, \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e, \u043d\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c: \u043f\u0440\u0438 \u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u043f\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0440\u0435\u0434\u043a\u043e\u0435 \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u0435 \u0432 \u043a\u044d\u0448. \u0415\u0441\u043b\u0438 <code>map<\/code> \u0445\u0440\u0430\u043d\u0438\u0442 \u0432\u0441\u0451 (\u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e) \u043d\u0435 \u043d\u0430 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u0445, \u0430 \u043f\u043e\u0434\u0440\u044f\u0434, \u0442\u043e \u0432 \u043c\u043e\u0435\u0439 \u043a\u0443\u0447\u0435 \u044d\u0442\u043e \u043f\u043e\u043a\u0430 \u043d\u0435 \u0442\u0430\u043a (\u0438 \u0435\u0441\u0442\u044c \u043d\u0430\u0434 \u0447\u0435\u043c \u043f\u043e\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c). \u0416\u0434\u0438\u0442\u0435 \u0441\u0442\u0430\u0442\u044c\u044e &#171;\u041a\u0430\u043a \u044f \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u0430\u043b \u0411\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0443\u044e \u043a\u0443\u0447\u0443 \u0441 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438 \u0432\u044b\u0438\u0433\u0440\u0430\u043b \u043a\u0443\u0447\u0443 \u0432\u0440\u0435\u043c\u0435\u043d\u0438&#187;.<\/p>\n<p>\u041a\u0430\u043a \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0445\u043e\u0440\u043e\u0448\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u043f\u0440\u0438, \u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0431\u044b, \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<h3>\u041f\u043e\u0436\u0435\u043b\u0430\u043d\u0438\u044f \u043e\u0442 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439<\/h3>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u044d\u0442\u043e \u0431\u044b\u043b\u0430 \u043c\u043e\u044f \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440\u0435, \u044f \u0431\u044b\u043b \u0431\u044b \u0440\u0430\u0434, \u0435\u0441\u043b\u0438 \u0431\u044b \u0432\u044b \u0441\u043c\u043e\u0433\u043b\u0438 \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u044c \u0441\u0432\u043e\u0438 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0447\u0438\u0435 \u043f\u043b\u044e\u0448\u043a\u0438. \u0422\u043e\u0433\u0434\u0430 \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u044e\u0441\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u043d\u0442\u0435\u043d\u0442.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/578252\/\"> https:\/\/habr.com\/ru\/articles\/578252\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h3>\u041e\u0433\u043b\u0430\u0432\u043b\u0435\u043d\u0438\u0435<\/h3>\n<ul>\n<li>\n<p>\u041a\u0430\u043a \u044f \u043d\u0430\u0447\u0430\u043b \u044d\u0442\u0443 \u0437\u0430\u0442\u0435\u044e<\/p>\n<\/li>\n<li>\n<p>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430?<\/p>\n<\/li>\n<li>\n<p>\u041a\u0430\u043a \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0441\u0432\u043e\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/p>\n<\/li>\n<li>\n<p>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e map \u0432 c++<\/p>\n<\/li>\n<li>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043c\u043e\u043c<\/p>\n<\/li>\n<li>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0438<\/p>\n<\/li>\n<li>\n<p>\u041d\u043e\u0432\u044b\u0435 \u0442\u0435\u0441\u0442\u044b<\/p>\n<\/li>\n<li>\n<p>\u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e \u0442\u0435\u0441\u0442\u0430\u043c \u0432 \u0438\u0442\u043e\u0433\u0435: \u0440\u0435\u0430\u043b\u044c\u043d\u0430\u044f \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u043f\u0430\u043c\u044f\u0442\u044c<\/p>\n<\/li>\n<li>\n<p>\u0412 \u0447\u0451\u043c \u0436\u0435 \u043f\u043b\u043e\u0445\u043e \u043c\u043e\u0451 \u0440\u0435\u0448\u0435\u043d\u0438\u0435? \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0436\u0435 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0438 \u0432\u0441\u0435 \u0434\u0435\u043b\u0430<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0436\u0435\u043b\u0430\u043d\u0438\u044f \u043e\u0442 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439<\/p>\n<\/li>\n<\/ul>\n<h3>\u041a\u0430\u043a \u044f \u043d\u0430\u0447\u0430\u043b \u044d\u0442\u0443 \u0437\u0430\u0442\u0435\u044e<\/h3>\n<p>\u042f \u0441\u0435\u0439\u0447\u0430\u0441 \u0438\u0437\u0443\u0447\u0430\u044e \u043f\u0440\u043e\u0434\u0432\u0438\u043d\u0443\u0442\u044b\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0432 \u043e\u0434\u0438\u043d \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u044b\u0439 \u0432\u0435\u0447\u0435\u0440 \u044f \u0440\u0435\u0448\u0438\u043b \u0441\u043e\u0431\u0438\u0440\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043a \u0441\u0435\u0431\u0435 \u043d\u0430 <a href=\"https:\/\/github.com\/mdan2000\/algorithms-and-data-structures\" rel=\"noopener noreferrer nofollow\">\u0433\u0438\u0442\u0445\u0430\u0431 <\/a>(\u0438 \u0434\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u044d\u0442\u043e \u0434\u0435\u043b\u0430\u044e). \u0417\u0430\u0445\u043e\u0442\u0435\u043b \u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u0441\u0451 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u044b\u043c, \u0435\u0441\u043b\u0438 \u0447\u0442\u043e-\u0442\u043e \u043c\u043d\u0435 \u0440\u0435\u0437\u043a\u043e \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f, \u0442\u043e \u044f \u0441\u043c\u043e\u0433 \u0437\u0430 \u0441\u0447\u0438\u0442\u0430\u043d\u043d\u044b\u0435 \u0441\u0435\u043a\u0443\u043d\u0434\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0431\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438\u043b\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c. \u0417\u0432\u0443\u0447\u0438\u0442 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043d\u0430 \u043a\u043e\u043d\u0442\u0435\u0441\u0442\u044b \u0441 <a href=\"https:\/\/codeforces.com\/\" rel=\"noopener noreferrer nofollow\">codeforces<\/a>.<\/p>\n<p>\u042f \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0441\u044f \u0441 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430\u043c\u0438 \u0438 \u0440\u0435\u0448\u0438\u043b \u0437\u0434\u0435\u0441\u044c \u043f\u043e\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f \u043e\u043f\u044b\u0442\u043e\u043c \u0441 \u0442\u0435\u043c, \u043a\u0442\u043e \u0442\u0430\u043a\u0436\u0435, \u043a\u0430\u043a \u0438 \u044f, \u043c\u0430\u043b\u043e \u0437\u043d\u0430\u043a\u043e\u043c \u0441 \u043f\u0440\u043e\u043c. \u043f\u0440\u043e\u0433\u043e\u0439 \u0438 \u0434\u043e \u044d\u0442\u043e\u0433\u043e \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u0443\u0432\u043b\u0435\u043a\u0430\u043b\u0441\u044f \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u043d\u044b\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c.<\/p>\n<h3>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430?<\/h3>\n<p>\u041e\u0431 \u044d\u0442\u043e\u043c \u0443\u0436\u0435 \u043d\u0438 \u0440\u0430\u0437 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u043b\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043d\u0430 \u0441\u0430\u0439\u0442\u0435 <a href=\"https:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0418\u0422\u041c\u041e<\/a>, <a href=\"https:\/\/habr.com\/ru\/post\/135232\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a> \u0438 \u0435\u0449\u0451 \u0432 \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u044b\u0445 <a href=\"https:\/\/www.youtube.com\/watch?v=CeAjTL-Fshs\" rel=\"noopener noreferrer nofollow\">\u043b\u0435\u043a\u0446\u0438\u044f\u0445<\/a> \u043e\u0442 \u041c\u0430\u0432\u0440\u0438\u043d\u0430 \u041f\u0430\u0432\u043b\u0430 \u042e\u0440\u044c\u0435\u0432\u0438\u0447\u0430 (\u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 \u0435\u0433\u043e \u0432\u0438\u0434\u0435\u043e, \u043e\u043d\u043e \u043e\u0447\u0435\u043d\u044c \u043a\u0440\u0443\u0442\u043e\u0435!).<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043a\u043e\u0440\u043e\u0442\u043a\u043e, \u0442\u043e \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0443\u0447\u0430 &#8212; \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e\u043c, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0441 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442\u043e\u043c.<\/p>\n<p>\u0412 \u043a\u0443\u0447\u0435, \u0433\u0434\u0435 \u0443 \u043d\u0430\u0441\u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/p>\n<ul>\n<li>\n<p>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0432 \u043a\u0443\u0447\u0443 \u0437\u0430(\u0430\u043c\u043e\u0440\u0442\u0438\u0437\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f)<\/p>\n<\/li>\n<li>\n<p>\u0412\u0437\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u0437\u0430(\u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438, \u0432 \u043c\u043e\u0435\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u044d\u0442\u043e \u0442\u0430\u043a)<\/p>\n<\/li>\n<li>\n<p>\u0418\u0437\u044a\u044f\u0442\u0438\u0435 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u0430 \u0437\u0430<\/p>\n<\/li>\n<\/ul>\n<p>\u0418 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c, \u0435\u0441\u0442\u044c \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e, \u0435\u0441\u043b\u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0441 \u043e\u0431\u044b\u0447\u043d\u043e\u0439 \u043a\u0443\u0447\u0435\u0439! \u0412 \u0431\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c merge \u0434\u0432\u0443\u0445 \u043a\u0443\u0447 \u0437\u0430 . \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u044d\u0442\u043e \u0431\u044b\u0432\u0430\u0435\u0442 \u043f\u043e\u043b\u0435\u0437\u043d\u043e \u00a0\u00af\\_(\u30c4)_\/\u00af<\/p>\n<h3>\u041a\u0430\u043a \u044f \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b \u0441\u0432\u043e\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/h3>\n<p>\u0417\u0434\u0435\u0441\u044c \u043f\u043e\u043c\u043e\u0433 <a href=\"https:\/\/codeforces.com\/\" rel=\"noopener noreferrer nofollow\">codeforces<\/a> \u0441 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 <a href=\"https:\/\/polygon.codeforces.com\/\" rel=\"noopener noreferrer nofollow\">polygon<\/a>. \u0417\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<figure class=\"full-width\"><figcaption>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/figcaption><\/figure>\n<figure class=\"full-width\"><figcaption>\u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0432\u043e\u0434\u0430 \u0438 \u0432\u044b\u0432\u043e\u0434\u0430<\/figcaption><\/figure>\n<p>\u0421\u0434\u0435\u043b\u0430\u043d\u044b \u044d\u0442\u0438 &#171;\u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u044b&#187; \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0442\u0435\u0441\u0442\u044b \u0431\u044b\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0438 \u0435\u0441\u043b\u0438 \u0431\u044b\u043b\u0430 \u043a\u0430\u043a\u0430\u044f-\u0442\u043e \u0431\u0430\u0433\u0430, \u0442\u043e \u043e\u043d\u0430 \u0432\u044b\u044f\u0441\u043d\u0438\u043b\u0430\u0441\u044c. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0442\u0435\u0441\u0442\u043e\u0432 \u0431\u044b\u043b\u043e 14 (\u0438 \u0432 \u0442\u0435\u0447\u0435\u043d\u0438\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u043f\u043e\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f).<\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e map \u0432 c++<\/h3>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"cpp\">#include &lt;iostream> #include &lt;map> #include &lt;string>   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int t; cin >> t;     while(t--) {         map&lt;int, int> heap;         int n; cin >> n;         for (int i = 0; i &lt; n; ++i) {             string op;             cin >> op;             if (op == \"Insert\") {                 int x;                 cin >> x;                 heap[x]++;             } else if (op == \"GetMin\") {                 cout &lt;&lt; heap.begin()->first &lt;&lt; '\\n';             } else if (op == \"EraseMin\") {                 heap.begin()->second--;                 if (heap.begin()->second == 0) {                     heap.erase(heap.begin());                 }             }         }     }     return 0; }<\/code><\/pre>\n<p>\u041f\u0440\u043e\u0441\u0442\u043e \u0437\u0430\u0432\u043e\u0434\u0438\u0442\u0441\u044f <code>map&lt;int, int><\/code> , \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0432\u0435\u0434\u0451\u0442\u0441\u044f \u043f\u043e\u0434\u0441\u0447\u0451\u0442 \u043a\u043e\u043b-\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e <code>map<\/code> \u0445\u0440\u0430\u043d\u0438\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0442\u0430\u043a, \u0447\u0442\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430 \u043e\u0442 begin \u0434\u043e end \u043e\u043d\u0438 \u0431\u0443\u0434\u0443\u0442 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u044f \u043a\u043b\u044e\u0447\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0437\u0430, \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0437\u0430. \u0415\u0441\u043b\u0438 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0435\u043f\u0435\u0440\u044c\u0440\u0430\u0437, \u0442\u043e \u043e\u043d \u0443\u0434\u0430\u043b\u044f\u0435\u0442\u0441\u044f \u0438\u0437 <code>map<\/code> , \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u0430\u043c\u044f\u0442\u044c \u0438 \u043d\u0435 \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438.<\/p>\n<p>\u041f\u0440\u043e\u0448\u0443 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0442\u0443\u0442 \u043d\u0435 \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 <code>set<\/code>, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044b (\u043f\u0440\u043e <code>multiset<\/code> \u0430\u0432\u0442\u043e\u0440 \u0440\u0435\u0448\u0438\u043b \u0442\u0430\u043a\u0442\u0438\u0447\u043d\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u0442\u044c).<\/p>\n<h3>\u041f\u0435\u0440\u0432\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043c\u043e\u043c<\/h3>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0430\u0432\u0430\u043b\u0430 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0443 \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b\u0430 \u0442\u0430\u043a:<\/p>\n<details class=\"spoiler\">\n<summary>\u041a\u043e\u043c\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"cpp\">#include &lt;memory> #include &lt;cassert> #include &lt;functional> #include &lt;iostream> #include &lt;algorithm> #include &lt;list> #include &lt;stdexcept>   template&lt;typename T> class BinHeap { private: struct BinHeapNode { T key; std::list&lt;std::shared_ptr&lt;BinHeapNode>> childs; size_t degree = 0; };   std::shared_ptr&lt;BinHeapNode> MergeEqualHeap(std::shared_ptr&lt;BinHeapNode> l, std::shared_ptr&lt;BinHeapNode> r) const { if (!cmp(l->key, r->key)) { swap(l, r); } l->childs.insert(l->childs.end(), r); l->degree++; return l; }   public: BinHeap() : size_(0) {};   BinHeap(const std::function&lt;bool(T, T)>&amp; cmpFunc) : size_(0), cmp(cmpFunc) {};   BinHeap(std::list&lt;std::shared_ptr&lt;BinHeapNode>>&amp; newChilds, const std::function&lt;bool(T, T)>&amp; cmpFunc) : cmp(cmpFunc) { Heap_ = newChilds; size_t newSize_ = 0; for (const auto&amp; c : Heap_) { newSize_ += (1u &lt;&lt; c->degree); } size_ = newSize_; }   void push(const T&amp; newKey) { std::shared_ptr&lt;BinHeapNode> node = std::make_shared&lt;BinHeapNode>(); node->key = newKey; auto it = Heap_.begin(); while (it != Heap_.end() &amp;&amp; (*it)->degree == node->degree) { if (cmp((*it)->key, node->key)) { (*it)->childs.insert((*it)->childs.end(), node); (*it)->degree++; node = *it; it = Heap_.erase(it); } else { node->childs.insert(node->childs.end(), *it); node->degree++; } } Heap_.insert(it, node); ++size_; }   void Merge(BinHeap&amp; r) { auto l = *this; auto itl = l.Heap_.begin(); auto itr = r.Heap_.begin(); std::list&lt;std::shared_ptr&lt;BinHeapNode>> newHeap; while (itl != l.Heap_.end() &amp;&amp; itr != r.Heap_.end()) { if ((*itl)->degree == (*itr)->degree) { newHeap.insert(newHeap.end(), MergeEqualHeap(*itl, *itr)); itl = l.Heap_.erase(itl); itr = r.Heap_.erase(itr); } else if (!newHeap.empty() &amp;&amp; (*itl)->degree == newHeap.back()->degree) { auto node = newHeap.back(); newHeap.pop_back(); newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itl)); itl = l.Heap_.erase(itl); } else if (!newHeap.empty() &amp;&amp; (*itr)->degree == newHeap.back()->degree) { auto node = newHeap.back(); newHeap.pop_back(); newHeap.insert(newHeap.end(), MergeEqualHeap(node, *itr)); itr = r.Heap_.erase(itr); } else { if (cmp((*itl)->key, (*itr)->key)) { newHeap.insert(newHeap.end(), *itl); itl = l.Heap_.erase(itl); } else { newHeap.insert(newHeap.end(), *itr); itr = r.Heap_.erase(itr); } } }   while (itl != l.Heap_.end()) { newHeap.insert(newHeap.end(), *itl); itl = l.Heap_.erase(itl); }   while (itr != r.Heap_.end()) { newHeap.insert(newHeap.end(), *itr); itr = r.Heap_.erase(itr); } Heap_ = newHeap; }   size_t size() const { return size_; }   T top() const { if (Heap_.empty()) { return {}; \/\/ throw??? } T res = Heap_.front()->key; for (const auto&amp; node : Heap_) { if (cmp(node->key, res)) { res = node->key; } } return res; }   void pop() { if (Heap_.empty()) { throw std::runtime_error(\"Erase from empty BinHeap\"); } auto minEl = Heap_.begin(); for (auto it = Heap_.begin(); it != Heap_.end(); ++it) { if (cmp((*it)->key, (*minEl)->key)) { minEl = it; } } BinHeap&lt;T> newHeap((*minEl)->childs, cmp); Heap_.erase(minEl); this->Merge(newHeap); }   private: size_t size_; std::list&lt;std::shared_ptr&lt;BinHeapNode>> Heap_; std::function&lt;bool(T, T)> cmp = [](const T&amp; l, const T&amp; r) { return l &lt; r; }; };   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     int t; cin >> t;     while(t--) {         BinHeap&lt;int> heap;         int n; cin >> n;         for (int i = 0; i &lt; n; ++i) {             string op;             cin >> op;             if (op == \"Insert\") {                 int x;                 cin >> x;                 heap.push(x);             } else if (op == \"GetMin\") {                 cout &lt;&lt; heap.top() &lt;&lt; endl;             } else if (op == \"EraseMin\") {                 heap.pop();             }         }     }     return 0; }<\/code><\/pre>\n<\/div>\n<\/details>\n<p>\u042d\u0442\u043e \u0434\u0430\u0432\u0430\u043b\u043e ML (Memory Limit) \u043d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0442\u0435\u0441\u0442\u0435. \u041f\u0440\u043e\u0442\u0435\u0447\u043a\u0430 \u0431\u044b\u043b\u0430 \u0437\u043d\u0430\u0442\u043d\u0430\u044f \u0438 \u043c\u043e\u0435\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u043e\u0439 \u043e\u0442 \u043d\u0435\u0451 \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0443\u0434\u0430\u043b\u044f\u0442\u044c \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043a\u0443\u0447\u0438, \u043f\u043e\u043a\u0430 \u043e\u043d\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430\u044f. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u043c\u0435\u0442\u043e\u0434 <code>empty()<\/code> (\u043d\u0430\u0434\u0435\u044e\u0441\u044c \u0432\u0441\u0435 \u0434\u043e\u0433\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u043e\u043d \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b) \u0438 \u044f \u0434\u0435\u043b\u0430\u043b <code>pop()<\/code> \u0434\u043e \u0442\u043e\u0433\u043e \u043c\u043e\u043c\u0435\u043d\u0442\u0430, \u043f\u043e\u043a\u0430 \u043a\u0443\u0447\u0430 \u043d\u0435 \u043f\u0443\u0441\u0442\u0430\u044f \u043f\u0435\u0440\u0435\u0434 \u0442\u0435\u043c, \u043a\u0430\u043a \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0441 \u043d\u0435\u0439 \u0440\u0430\u0431\u043e\u0442\u0443.<\/p>\n<p>\u0417\u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u043e? \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0431\u044b\u043b\u043e \u0432\u0441\u0451 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e: \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 map \u0437\u0430\u0445\u043e\u0434\u0438\u043b\u043e \u0437\u0430 498ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0437\u0430 842ms. \u041d\u043e \u0441\u0430\u043c\u044b\u0439 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0442\u0435\u0441\u0442 \u0431\u044b\u043b \u0442\u0430\u043a\u043e\u0432, \u0447\u0442\u043e \u0431\u044b\u043b\u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u043e\u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442\u0435. \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043c\u043e\u0439 \u0441\u043e\u0441\u0435\u0434, \u0413\u0435\u043e\u0440\u0433\u0438\u0439 \u0428\u0443\u043a\u0430\u043b\u043e\u0432, \u0433\u043e\u0432\u043e\u0440\u0438\u0442 \u043c\u043d\u0435<\/p>\n<blockquote>\n<p>\u0414\u0430\u043d\u044f, \u0442\u0430\u043a \u044d\u0442\u043e \u0436\u0435 \u0444\u0438\u0433\u043d\u044f, \u0434\u0430\u0432\u0430\u0439 \u043e\u0434\u0438\u043d \u0442\u0435\u0441\u0442 \u043d\u0430\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439<\/p>\n<\/blockquote>\n<p>\u042f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u044d\u0442\u043e\u0442 \u0442\u0435\u0441\u0442 (15-\u0439 \u0442\u0435\u0441\u0442). \u041f\u043e\u0441\u043b\u0435 \u0447\u0435\u0433\u043e \u043f\u0440\u0438\u0448\u043b\u043e\u0441\u044c \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e. \u0412 \u0442\u0435\u043e\u0440\u0438\u0438, \u0432\u0441\u0451 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u043e\u0434\u0438\u043d \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043c\u0438\u043d\u0438-\u0442\u0435\u0441\u0442 \u043d\u0430\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, map \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043b \u0437\u0430 1045ms, \u0430 \u043c\u043e\u044f \u043a\u0443\u0447\u0430 \u0441\u0442\u0430\u043b\u0430 \u0432\u044b\u0434\u0430\u0432\u0430\u0442\u044c TL (Time Limit) \u043d\u0430 15-\u043c \u0442\u0435\u0441\u0442\u0435 (\u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u043d\u0430 \u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442 \u0442\u0435\u0441\u0442, \u043a\u0430\u043a \u0440\u0430\u0437 \u0432 \u0442\u043e\u043c, \u0433\u0434\u0435 \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u0443\u0447\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439).<\/p>\n<h3>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u043e\u0442\u0435\u0447\u043a\u0438<\/h3>\n<p>\u0412\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u043b\u0430 \u0442\u0430\u043a<\/p>\n<details class=\"spoiler\">\n<summary>\u0412\u0442\u043e\u0440\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"cpp\">#include &lt;memory> #include &lt;cassert> #include &lt;functional> #include &lt;iostream> #include &lt;algorithm> #include &lt;list> #include &lt;stdexcept> #include &lt;unordered_set> #include &lt;queue>   template&lt;typename T> class BinHeap { private:     struct BinHeapNode {         T key;         std::list&lt;std::shared_ptr&lt;BinHeapNode>> childs;         size_t degree = 0;     };       std::shared_ptr&lt;BinHeapNode> MergeEqualHeap(std::shared_ptr&lt;BinHeapNode> l, std::shared_ptr&lt;BinHeapNode> r) const {         if (!cmp(l->key, r->key)) {             swap(l, r);         }         l->childs.insert(l->childs.end(), r);         l->degree++;         return l;     }   public:     BinHeap() : size_(0) {};       BinHeap(const std::function&lt;bool(T, T)>&amp; cmpFunc) :         size_(0),         cmp(cmpFunc) {};       void push(const T&amp; newKey) {           std::shared_ptr&lt;BinHeapNode> node = std::make_shared&lt;BinHeapNode>();         node->key = newKey;         auto it = Heap_.begin();         while (it != Heap_.end() &amp;&amp; (*it)->degree == node->degree) {             if (cmp((*it)->key, node->key)) {                 (*it)->childs.insert((*it)->childs.end(), node);                 (*it)->degree++;                 node = *it;             }             else {                 node->childs.insert(node->childs.end(), *it);                 node->degree++;             }             if (it == MinNode_) {                 MinNode_ = Heap_.end();             }             it = Heap_.erase(it);         }         if (MinNode_ == Heap_.end() || cmp(node->key, (*MinNode_)->key)) {             MinNode_ = Heap_.insert(it, node);         }         else {             Heap_.insert(it, node);         }         ++size_;     }       void Merge(std::list&lt;std::shared_ptr&lt;BinHeapNode>>&amp; r) {        <\/code><\/pre>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-399808","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/399808","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=399808"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/399808\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=399808"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=399808"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=399808"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}