{"id":3506,"date":"2017-12-26T00:53:51","date_gmt":"2017-12-25T21:53:51","guid":{"rendered":"http:\/\/java.mazurok.com\/?p=3506"},"modified":"2017-12-26T01:26:59","modified_gmt":"2017-12-25T22:26:59","slug":"e-olymp4491-%d1%82%d1%80%d0%be%d0%b5-%d0%b8%d0%b7-%d0%bf%d1%80%d0%be%d1%81%d1%82%d0%be%d0%ba%d0%b2%d0%b0%d1%88%d0%b8%d0%bd%d0%be","status":"publish","type":"post","link":"https:\/\/java.mazurok.com\/?p=3506","title":{"rendered":"e-olymp4491 \u0422\u0440\u043e\u0435 \u0438\u0437 \u041f\u0440\u043e\u0441\u0442\u043e\u043a\u0432\u0430\u0448\u0438\u043d\u043e"},"content":{"rendered":"<p><em>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438:<\/em><br \/>\n<em>&#8212; \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u044f \u043d\u0430\u0443\u0447\u0438\u043b\u0441\u044f \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432.<br \/>\n&#8212; \u041f\u043e\u0434\u043e\u0436\u0434\u0438, \u0428\u0430\u0440\u0438\u043a, \u044f \u0437\u0430\u043d\u044f\u0442.<br \/>\n&#8212; \u041d\u0443 \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u043d\u0443 \u0441\u043c\u043e\u0442\u0440\u0438 \u043a\u0430\u043a\u043e\u0439 \u044f \u043a\u043e\u0434 \u043d\u0430\u043f\u0438\u0441\u0430\u043b:<\/em><\/p>\n<pre class=\"lang:c++ decode:true \">int build(int v, int left, int right) {\r\n\tif (left == right) {\r\n\t\tt[v] = a[left];\r\n\t\treturn 0;\r\n\r\n\t}\r\n\tint mid = (left+right) \/ 2;\r\n\tbuild(v*2, left, mid);\r\n\tbuild(v*2+1, mid+1, right);\r\n\tt[v] = max(t[v*2], t[v*2+1]);\r\n\treturn 0;\r\n}\r\n\r\nint get_max(int v, int left, int right, int lpos, int rpos) {\r\n\tif (left == lpos &amp;&amp; right == rpos)\r\n\t\treturn t[v];\r\n\tif (lpos &gt; rpos)\r\n\t\treturn -1;\r\n\tint mid = (left+right) \/ 2;\r\n\treturn max(get_max(v*2, left, mid, lpos, min(rpos, mid)),\r\n\tget_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));\r\n}<\/pre>\n<p><em>&#8212; \u041d\u0443 \u0445\u043e\u0440\u043e\u0448\u043e, \u0428\u0430\u0440\u0438\u043a, \u0440\u0430\u0437 \u0442\u044b \u0442\u0430\u043a \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0441\u044f \u0441 \u044d\u0442\u043e\u0439 \u0442\u0435\u043c\u043e\u0439, \u0434\u0430\u0432\u0430\u0439 \u044f \u0442\u0435\u0431\u0435 \u0434\u0430\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 [latex]n[\/latex] \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438 \u0447\u0438\u0441\u043b\u043e [latex]k[\/latex], \u0430 \u0442\u044b \u043c\u043d\u0435 \u0441\u043a\u0430\u0436\u0435\u0448\u044c \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u0438\u0445 \u043f\u0430\u0440 [latex]l;r \\left ( 1\\leq l\\leq r\\leq n \\right ),[\/latex] \u0447\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u0432\u044b\u0437\u0432\u0430\u043d\u043d\u0430\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p>                                      [latex]get[\/latex]_[latex]max(1, 1, n, l, r)[\/latex]\n<p>\u0432\u0435\u0440\u043d\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0432\u043d\u043e\u0435 [latex]k[\/latex]. \u041c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043f\u0435\u0440\u0435\u0434 \u044d\u0442\u0438\u043c \u0431\u044b\u043b\u0430 \u0432\u044b\u0437\u0432\u0430\u043d\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f<\/p>\n<p>                                          [latex]build(1, 1, n)[\/latex]\n<p>&#8212; \u0425\u043e\u0440\u043e\u0448\u043e, \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440!<\/em><\/p>\n<p><em>\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435:<\/em><br \/>\n\u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0447\u0438\u0441\u043b\u043e [latex]n \\left ( 1\\leq n\\leq 10^{6} \\right )[\/latex] &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438 [latex]k \\left ( 1\\leq k\\leq 10^{9} \\right )[\/latex] &#8212; \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044f. \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f [latex]n[\/latex] \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0449\u0438\u0445 [latex]10^{9}[\/latex] &#8212; \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u0430\u0441\u0441\u0438\u0432\u0430.<\/p>\n<p><em>\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435:<\/em><br \/>\n\u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u2013 \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0443.<\/p>\n<p><em>\u0422\u0435\u0441\u0442\u044b:<\/em><\/p>\n<table>\n<tr>\n<td colspan=\"3\">\u0412\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n<td>\u0412\u044b\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435<\/td>\n<tr>\n<td>[latex]n[\/latex]<\/td>\n<td>[latex]k[\/latex]<\/td>\n<td>[latex]elem[\/latex]_[latex]tree[][\/latex]<\/td>\n<td>[latex]ans[\/latex]<\/td>\n<tr>\n<td>5<\/td>\n<td>3<\/td>\n<td>1 2 3 2 3<\/td>\n<td>11<\/td>\n<tr>\n<td>10<\/td>\n<td>6<\/td>\n<td>1 4 7 6 2 4 1 9 6 6<\/td>\n<td>7<\/td>\n<tr>\n<td>20<\/td>\n<td>15<\/td>\n<td>5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6<\/td>\n<td>43<\/td>\n<\/table>\n<p><em>\u041a\u043e\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b:<\/em><\/p>\n<pre class=\"lang:java decode:true \">import java.util.*;\r\n\r\npublic class Main\r\n{\r\n  public static void main(String[] args) \r\n  {\r\n    Scanner in = new Scanner(System.in);\r\n    int n = in.nextInt();\r\n    int k = in.nextInt();\r\n    int[] elem_tree = new int[n];\r\n    int ans=0, left=0, right=0;\r\n    for(int i=0; i&lt;n; i++){\r\n    \telem_tree[i]=in.nextInt();\r\n    \tif (elem_tree[i]==k){\r\n    \t\tans+=i-left+1;\r\n    \t\tright=i;\r\n    \t}\r\n    \telse{\r\n    \t\tif(elem_tree[i]&gt;k){\r\n        \t\t\tright=0;\r\n        \t\t\tleft=i+1;\r\n    \t\t}\r\n    \t\telse if(elem_tree[i]&lt;k &amp;&amp; right!=0) ans+=right-left+1;\r\n    \t}\r\n    }\r\n    System.out.println(ans);\r\n  }\r\n}<\/pre>\n<p><em>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u044f:<\/em><br \/>\n\u0417\u0430\u0434\u0430\u0434\u0438\u043c \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0433\u0440\u0430\u043d\u0438\u0446\u044b [latex]\\left [ left, right \\right ][\/latex]. \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u043e\u0431\u0430 \u043a\u043e\u043d\u0446\u0430 \u043d\u0443\u043b\u0435\u043c. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 [latex]elem\\_tree\\left [ i \\right ][\/latex] \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0435. \u0422\u043e\u0433\u0434\u0430 \u0435\u0441\u043b\u0438 [latex]elem\\_tree\\left [ i \\right ]=k[\/latex], \u0442\u043e \u043d\u0430 \u0432\u0441\u0435\u043c \u043e\u0442\u0440\u0435\u0437\u043a\u0435 \u043e\u0442 [latex]left[\/latex] \u0434\u043e [latex]i[\/latex] \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u043e\u043c \u0431\u0443\u0434\u0435\u0442 [latex]k[\/latex]. \u0423\u0432\u0435\u043b\u0438\u0447\u0438\u043c \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 [latex]left[\/latex] \u0438 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0435\u0433\u043e \u0440\u0430\u0432\u043d\u044b\u043c [latex]i[\/latex], \u043f\u0440\u0438\u0447\u0435\u043c [latex]right=0.[\/latex] \u0415\u0441\u043b\u0438 [latex]elem\\_tree\\left [ i \\right ]\\lt k[\/latex], \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0431\u0443\u0434\u0435\u0442 \u0442\u0430\u043a\u0436\u0435 \u0440\u0430\u0432\u0435\u043d [latex]k[\/latex]. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e [latex]right.[\/latex] \u0415\u0441\u043b\u0438 \u0436\u0435 [latex]elem\\_tree\\left [ i \\right ]\\gt k[\/latex] , \u0442\u043e [latex]left[\/latex] \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0440\u0430\u0432\u043d\u044b\u043c [latex]i+1[\/latex], \u0430 [latex]right[\/latex] \u043e\u0431\u043d\u0443\u043b\u044f\u0435\u043c.<br \/>\n\u041f\u0440\u043e\u0439\u0434\u044f \u043f\u043e \u0432\u0441\u0435\u043c\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0443, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f [latex]left[\/latex] \u0440\u0430\u0432\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043f\u0430\u0440 \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0440\u0430\u0432\u0435\u043d [latex]k[\/latex], \u0430 [latex]right[\/latex] \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u0442\u0430\u0442\u044c \u0440\u0430\u0432\u043d\u044b\u043c \u043d\u0443\u043b\u044e.<\/p>\n<p><a href=\"https:\/\/ideone.com\/BxlFQC\"><em>\u041a\u043e\u0434 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u043d\u0430 Java<\/em><\/a><br \/>\n<a href=\"https:\/\/www.e-olymp.com\/ru\/problems\/4491\"><em>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/em><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438: &#8212; \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u044f \u043d\u0430\u0443\u0447\u0438\u043b\u0441\u044f \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432. &#8212; \u041f\u043e\u0434\u043e\u0436\u0434\u0438, \u0428\u0430\u0440\u0438\u043a, \u044f \u0437\u0430\u043d\u044f\u0442. &#8212; \u041d\u0443 \u0414\u044f\u0434\u044f \u0424\u0435\u0434\u043e\u0440, \u043d\u0443 \u0441\u043c\u043e\u0442\u0440\u0438 \u043a\u0430\u043a\u043e\u0439 \u044f \u043a\u043e\u0434 \u043d\u0430\u043f\u0438\u0441\u0430\u043b: int build(int v, int left, int right) { if (left == right) { t[v] = a[left]; return 0; } int mid = (left+right) \/ 2; build(v*2, left, mid); &hellip; <a href=\"https:\/\/java.mazurok.com\/?p=3506\" class=\"more-link\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[110],"tags":[41,350],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/3506"}],"collection":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3506"}],"version-history":[{"count":20,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/3506\/revisions"}],"predecessor-version":[{"id":3526,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=\/wp\/v2\/posts\/3506\/revisions\/3526"}],"wp:attachment":[{"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3506"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3506"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java.mazurok.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}