Jekyll2020-10-24T19:42:03+00:00https://justicehui.github.io/rss/JusticeHui가 PS하는 블로그Let's solve problem with JusticeHui!JusticeHui백준14390 타일 놓기2020-10-25T04:26:00+00:002020-10-25T04:26:00+00:00https://justicehui.github.io/ps/2020/10/25/BOJ14390<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/14390</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>이분 매칭</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(NM \sqrt{NM})$</li> </ul> <h3 id="풀이">풀이</h3> <p><a href="https://codeforces.com/contest/1404/problem/E">Codeforces Round #668 Div.1 E</a>에 동일한 문제가 출제되었습니다.</p> <p>타일의 개수를 최소화하는 것은, 모서리를 최대한 많이 끊어내는 것으로 생각할 수 있습니다. 이때 정답은 (타일을 놓아야 하는 칸의 개수 - 끊은 모서리의 개수)가 됩니다.</p> <p>타일은 $1 \times K$ 꼴이기 때문에 각 덩어리가 꺾이면 안 됩니다.<br /> 따라서 아래 그림처럼 그래프를 만들고, 이 그래프에서 최대 독립 집합(Maximum Independent Set)의 크기를 구하면 됩니다.<br /> <img src="https://i.imgur.com/NQGBpAR.png" alt="" /></p> <p>이분 그래프에서 최대 독립 집합의 크기는 (정점 개수 - 최대 매칭 크기)이므로 Dinic이나 Hopcroft-Karp 등을 이용해 문제를 풀 수 잇습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">id</span><span class="p">[</span><span class="mi">222</span><span class="p">][</span><span class="mi">222</span><span class="p">][</span><span class="mi">2</span><span class="p">];</span> <span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">222</span><span class="p">][</span><span class="mi">222</span><span class="p">];</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">80800</span><span class="p">,</span> <span class="n">T</span> <span class="o">=</span> <span class="mi">80801</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">SZ</span> <span class="o">=</span> <span class="mi">80808</span><span class="p">;</span> <span class="k">struct</span> <span class="nc">Dinic</span><span class="p">{</span> <span class="k">using</span> <span class="n">FlowType</span> <span class="o">=</span> <span class="kt">int</span><span class="p">;</span> <span class="k">const</span> <span class="n">FlowType</span> <span class="n">flow_max</span> <span class="o">=</span> <span class="mf">1e9</span><span class="p">;</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">t</span><span class="p">;</span> <span class="c1">// source, sink;</span> <span class="k">struct</span> <span class="nc">Edge</span><span class="p">{</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="n">dual</span><span class="p">;</span> <span class="n">FlowType</span> <span class="n">c</span><span class="p">;</span> <span class="p">};</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">Edge</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="n">SZ</span><span class="p">];</span> <span class="kt">void</span> <span class="n">addEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="n">FlowType</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span><span class="p">){</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span><span class="n">e</span><span class="p">,</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">size</span><span class="p">(),</span> <span class="n">x</span><span class="p">});</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">({</span><span class="n">s</span><span class="p">,</span> <span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">});</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">lv</span><span class="p">[</span><span class="n">SZ</span><span class="p">],</span> <span class="n">work</span><span class="p">[</span><span class="n">SZ</span><span class="p">];</span> <span class="kt">bool</span> <span class="n">bfs</span><span class="p">(){</span> <span class="n">memset</span><span class="p">(</span><span class="n">lv</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">lv</span><span class="p">);</span> <span class="n">queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="n">lv</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="o">!</span><span class="n">q</span><span class="p">.</span><span class="n">empty</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">lv</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">i</span><span class="p">.</span><span class="n">c</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">){</span> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">);</span> <span class="n">lv</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">lv</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="n">lv</span><span class="p">[</span><span class="n">t</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">FlowType</span> <span class="n">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">tot</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">v</span> <span class="o">==</span> <span class="n">t</span><span class="p">)</span> <span class="k">return</span> <span class="n">tot</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="o">&amp;</span><span class="n">_i</span><span class="o">=</span><span class="n">work</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="n">_i</span><span class="o">&lt;</span><span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">size</span><span class="p">();</span> <span class="n">_i</span><span class="o">++</span><span class="p">){</span> <span class="n">Edge</span> <span class="o">&amp;</span><span class="n">i</span> <span class="o">=</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">][</span><span class="n">_i</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">lv</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">]</span> <span class="o">==</span> <span class="n">lv</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">i</span><span class="p">.</span><span class="n">c</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">){</span> <span class="kt">int</span> <span class="n">fl</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">,</span> <span class="n">min</span><span class="p">(</span><span class="n">tot</span><span class="p">,</span> <span class="n">i</span><span class="p">.</span><span class="n">c</span><span class="p">));</span> <span class="k">if</span><span class="p">(</span><span class="n">fl</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">){</span> <span class="n">i</span><span class="p">.</span><span class="n">c</span> <span class="o">-=</span> <span class="n">fl</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">v</span><span class="p">][</span><span class="n">i</span><span class="p">.</span><span class="n">dual</span><span class="p">].</span><span class="n">c</span> <span class="o">+=</span> <span class="n">fl</span><span class="p">;</span> <span class="k">return</span> <span class="n">fl</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="n">FlowType</span> <span class="n">run</span><span class="p">(</span><span class="kt">int</span> <span class="n">_s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">_t</span><span class="p">){</span> <span class="n">s</span> <span class="o">=</span> <span class="n">_s</span><span class="p">;</span> <span class="n">t</span> <span class="o">=</span> <span class="n">_t</span><span class="p">;</span> <span class="n">FlowType</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">bfs</span><span class="p">()){</span> <span class="n">memset</span><span class="p">(</span><span class="n">work</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">work</span><span class="p">);</span> <span class="n">FlowType</span> <span class="n">tmp</span><span class="p">;</span> <span class="k">while</span><span class="p">((</span><span class="n">tmp</span> <span class="o">=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">flow_max</span><span class="p">)))</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">tmp</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">flow</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="kt">int</span> <span class="n">pv</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'.'</span><span class="p">)</span> <span class="p">{</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'.'</span><span class="p">)</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">,</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">pv</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'.'</span><span class="p">)</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">,</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">pv</span><span class="p">,</span> <span class="n">T</span><span class="p">);</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'.'</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">1</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">])</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">]);</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">]){</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">])</span> <span class="n">flow</span><span class="p">.</span><span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">],</span> <span class="n">id</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="mi">1</span><span class="p">]);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">cnt</span> <span class="o">-</span> <span class="p">(</span><span class="n">pv</span> <span class="o">-</span> <span class="n">flow</span><span class="p">.</span><span class="n">run</span><span class="p">(</span><span class="n">S</span><span class="p">,</span> <span class="n">T</span><span class="p">));</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/14390백준2423 전구를 켜라2020-10-25T04:24:00+00:002020-10-25T04:24:00+00:00https://justicehui.github.io/boi/2020/10/25/BOJ2423<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/2423</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2011 BalticOI 3번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>다익스트라</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$NM \log (NM)$</li> </ul> <h3 id="풀이">풀이</h3> <p>간단한 다익스트라(또는 01 BFS) 문제입니다.<br /> 교육용으로 좋을 것 같습니다.</p> <p>각 꼭짓점을 정점으로 잡고, 서로 대각선 방향으로 마주보고 있는 두 정점을 가중치가 0 또는 1인 간선으로 연결해주면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="kr">inline</span> <span class="kt">int</span> <span class="nf">id</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="k">return</span> <span class="n">i</span><span class="o">*</span><span class="mi">555</span><span class="o">+</span><span class="n">j</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">555</span><span class="p">][</span><span class="mi">555</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">303030</span><span class="p">];</span> <span class="kt">int</span> <span class="n">dst</span><span class="p">[</span><span class="mi">303030</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">addEdge</span><span class="p">(</span><span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'/'</span><span class="p">){</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">),</span> <span class="mi">1</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="p">),</span> <span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="mi">0</span><span class="p">);</span> <span class="p">}</span> <span class="k">else</span><span class="p">{</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">),</span> <span class="mi">0</span><span class="p">);</span> <span class="n">addEdge</span><span class="p">(</span><span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="p">),</span> <span class="n">id</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">memset</span><span class="p">(</span><span class="n">dst</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">dst</span><span class="p">);</span> <span class="n">priority_queue</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">pq</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">emplace</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">id</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">));</span> <span class="n">dst</span><span class="p">[</span><span class="n">id</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">)]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">pq</span><span class="p">.</span><span class="n">size</span><span class="p">()){</span> <span class="kt">int</span> <span class="n">now</span> <span class="o">=</span> <span class="n">pq</span><span class="p">.</span><span class="n">top</span><span class="p">().</span><span class="n">y</span><span class="p">,</span> <span class="n">cst</span> <span class="o">=</span> <span class="o">-</span><span class="n">pq</span><span class="p">.</span><span class="n">top</span><span class="p">().</span><span class="n">x</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="n">cst</span> <span class="o">&gt;</span> <span class="n">dst</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">now</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">cst</span> <span class="o">+</span> <span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">){</span> <span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">cst</span> <span class="o">+</span> <span class="n">i</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">pq</span><span class="p">.</span><span class="n">emplace</span><span class="p">(</span><span class="o">-</span><span class="n">dst</span><span class="p">[</span><span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">],</span> <span class="n">i</span><span class="p">.</span><span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">res</span> <span class="o">=</span> <span class="n">dst</span><span class="p">[</span><span class="n">id</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">)];</span> <span class="k">if</span><span class="p">(</span><span class="n">res</span> <span class="o">&lt;</span> <span class="mf">1e9</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">;</span> <span class="k">else</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"NO SOLUTION"</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/2423백준10272 현상금 사냥꾼 김정은2020-10-24T04:20:00+00:002020-10-24T04:20:00+00:00https://justicehui.github.io/icpc/2020/10/24/10272<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/10272</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2014 GCPC C번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>DP</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^2)$</li> </ul> <h3 id="풀이">풀이</h3> <p>두 사람이 1에서 시작해 서로 다른 지점을 통해 N까지 간다고 생각하면 더 편합니다.</p> <p>$D(i, j)$를 첫번째 사람은 $i$번째 지점까지, 두번째 사람은 $j$번째 지점까지 가는 최단 거리라고 정의합시다.<br /> 두 사람 중 한 사람이 $\max(i, j) + 1$로 이동해야 하므로 상태 전이는 매우 간단하게 나타낼 수 있습니다.</p> <p>$O(N^2)$에 문제를 풀 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> <span class="n">p</span> <span class="n">a</span><span class="p">[</span><span class="mi">555</span><span class="p">];</span> <span class="kt">double</span> <span class="n">dp</span><span class="p">[</span><span class="mi">555</span><span class="p">][</span><span class="mi">555</span><span class="p">];</span> <span class="kt">double</span> <span class="nf">dst</span><span class="p">(</span><span class="n">p</span> <span class="n">s</span><span class="p">,</span> <span class="n">p</span> <span class="n">e</span><span class="p">){</span> <span class="n">ll</span> <span class="n">dx</span> <span class="o">=</span> <span class="n">s</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">e</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy</span> <span class="o">=</span> <span class="n">s</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">e</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">sqrt</span><span class="p">(</span><span class="n">dx</span><span class="o">*</span><span class="n">dx</span> <span class="o">+</span> <span class="n">dy</span><span class="o">*</span><span class="n">dy</span><span class="p">);</span> <span class="p">}</span> <span class="kt">double</span> <span class="nf">f</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">){</span> <span class="kt">double</span> <span class="o">&amp;</span><span class="n">res</span> <span class="o">=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">res</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="n">res</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">n</span><span class="p">)</span> <span class="k">return</span> <span class="n">res</span> <span class="o">=</span> <span class="n">dst</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">n</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">j</span> <span class="o">==</span> <span class="n">n</span><span class="p">)</span> <span class="k">return</span> <span class="n">res</span> <span class="o">=</span> <span class="n">dst</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">n</span><span class="p">]);</span> <span class="kt">int</span> <span class="n">k</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">res</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">f</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="n">j</span><span class="p">)</span> <span class="o">+</span> <span class="n">dst</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">]),</span> <span class="n">f</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">k</span><span class="p">)</span> <span class="o">+</span> <span class="n">dst</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">]));</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(){</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">555</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="mi">555</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">fixed</span> <span class="o">&lt;&lt;</span> <span class="n">setprecision</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span> <span class="o">&lt;&lt;</span> <span class="n">f</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">t</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">)</span> <span class="n">solve</span><span class="p">();</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/102722020/2021 COCI Contest #12020-10-23T16:35:00+00:002020-10-23T16:35:00+00:00https://justicehui.github.io/coci/2020/10/23/coci-1<h3 id="overview">Overview</h3> <p>3시간 5문제 셋입니다. 앞쪽 2문제는 난이도순, 나머지 3문제는 난이도 상관 없이 섞어놓은 것 같습니다.</p> <p>체감 난이도는 1 &lt; 2 &lt; 4 &lt; 5 &lt; 3 순입니다.<br /> 2번 문제는 <strong>KOI 고등부 1번</strong>, 3번 문제는 <strong>KOI 고등부 4번</strong>, 4번 문제는 <strong>KOI 중등부 3번</strong>, 5번 문제는 <strong>KOI 중등부 3번</strong> 정도의 난이도인 것 같습니다.<br /> 코드는 글 하단에 한 번에 올리겠습니다.</p> <p>문제 지문 : <a href="https://hsin.hr/coci/contest1_tasks.pdf">https://hsin.hr/coci/contest1_tasks.pdf</a></p> <h3 id="task-1-patkice-50점">Task 1. Patkice (50점)</h3> <h5 id="문제">문제</h5> <p>N by M 격자가 주어지고, o에서 출발해 x로 가려고 합니다.<br /> 처음 이동방향은 마음대로 정할 수 있고, 그 다음부터는 &lt; &gt; ^ v에 따라 이동 방향이 결정 됩니다. x로 도달할 수 있는지 판별하는 문제입니다.</p> <h5 id="풀이">풀이</h5> <p>단순 구현 문제입니다.</p> <h3 id="task-2-bajka-70점">Task 2. Bajka (70점)</h3> <h5 id="문제-1">문제</h5> <p>길이가 300 이하인 두 문자열 S와 T가 주어집니다. (두 문자열의 길이는 서로 다를 수 있습니다.)</p> <p>S의 임의의 위치에서 시작해 적절히 <strong>이동</strong>을 해서, 최소 거리만큼 이동해 T를 만드는 것이 목표입니다. 3가지 방법으로 이동할 수 있습니다.</p> <ol> <li>왼쪽으로 한 칸 이동하고 그 칸에 있는 문자를 T에 추가한다. 이때 이동 거리는 1이다.</li> <li>오른쪽으로 한 칸 이동하고 그 칸에 있는 문자를 T에 추가한다. 이때 이동 거리는 1이다.</li> <li>현재 칸과 동일한 문자가 적혀있는 칸으로 이동한다. x에서 y로 이동한다고 하면 이동 거리는 $\vert x - y \vert$ 이다.</li> </ol> <p>문자열을 만들 수 있는 경우에는 최소 거리를 출력하고, 그렇지 않은 경우에는 -1을 출력하는 문제입니다.</p> <h5 id="풀이-1">풀이</h5> <p><code class="language-plaintext highlighter-rouge">D(i, j) = T의 i번째 글자까지 완성했고, 현재 S의 j번째 위치에 있을 때 최소 이동 거리</code><br /> 로 DP를 정의하면 O(N^2M)에 문제를 풀 수 있습니다.</p> <h3 id="task-3-3d-histogram-110점">Task 3. 3D Histogram (110점)</h3> <h5 id="문제-2">문제</h5> <p>3차원 히스토그램에서 가장 부피가 큰 직육면체의 부피를 구하는 문제입니다.</p> <p>N ≤ 2000인 경우를 해결하면 20점을 받을 수 있고, N ≤ 2e5인 경우를 해결하면 90점을 추가로 받을 수 있습니다.</p> <h5 id="풀이-2">풀이</h5> <p>2차원의 경우는 매우 유명한 문제이고, 모노톤 스택을 이용한 풀이와 분할 정복을 이용한 풀이가 있습니다. 모노톤 스택을 이용하는 것은 어려울 것 같으니 분할 정복 풀이를 생각해봅시다.</p> <p>구간 [st, ed]에 대해 중점 md를 지나는 경우를 모두 처리한 뒤, 구간 [st, md-1]과 [md+1, ed]에 대해 재귀적으로 처리할 것입니다.</p> <p>두 함수 f(i, j)와 g(i, j)를 아래와 같이 정의합시다.<br /> $f(i, j) = \min_{i \leq k \leq j} (a_k), \ g(i, j) = \min_{i \leq k \leq j} (b_k)$</p> <p>f(st, ed) * g(st, ed) * (ed - st + 1)을 최대화 하는 것이 이 문제의 목표입니다.</p> <p>구간의 양 끝점 st, ed와 중간 지점 md에 대해, 4가지 경우로 분류할 수 있습니다.</p> <ol> <li>f(st, md) ≤ f(md, ed) &amp;&amp; g(st, md) ≤ g(md, ed)</li> <li>f(st, md) ≤ f(md, ed) &amp;&amp; g(st, md) ≥ g(md, ed)</li> <li>f(st, md) ≥ f(md, ed) &amp;&amp; g(st, md) ≥ g(md, ed)</li> <li>f(st, md) ≥ f(md, ed) &amp;&amp; g(st, md) ≤ g(md, ed)</li> </ol> <p>1, 2만 처리하면 적절히 뒤집고 swap하는 것으로 3, 4번을 똑같이 처리할 수 있습니다. 1, 2에 대한 풀이를 알아봅시다.</p> <p>1번 케이스는 투포인터로 O(ed - st + 1)만에 쉽게 해결할 수 있습니다.<br /> 각 시작점 s에 대해, f(s, e) = f(s, m)이고 g(s, e) = g(s, m)인 e의 최댓값을 찾아서 최대 부피를 갱신해주면 됩니다. (아래 코드에서 calc1 함수를 참고하세요.)</p> <p>2번 케이스는 복잡합니다.<br /> f(s, m) * g(m, e) * (e - s + 1)을 최대화 하는 것이 목적입니다.<br /> 식을 좀 변형하면, f(s, m) * (-s + 1) * g(m, e) + f(s, m) * e * g(m, e)가 됩니다.<br /> f(s, m)으로 묶어주면, f(s, m) * { g(m, e) * (-s + 1) + e * g(m, e) }가 됩니다.</p> <p>중괄호 안쪽의 식은 g(m, e)를 기울기, e*g(m, e)를 y절편으로 하는 일차함수라고 생각할 수 있습니다. 일차함수의 최댓값을 구하는 것은 Convex Hull Trick을 이용해 빠르게 구할 수 있으니, 이 성질을 이용해서 풀이를 찾아봅시다.</p> <p>먼저 1번 케이스처럼 각 시작점 s에 대해, f(s, e) = f(s, m)이고 g(s, e) = g(s, m)이 되도록 하는 e의 <strong>구간</strong>을 각각 전처리해줍시다. O(ed - st + 1) 시간에 가능합니다. 이 구간을 l(s), r(s)라고 합시다.</p> <p>각 시작점 s에 대해, l(s)부터 r(s)번째 직선들 중에서 (-l + 1) 시점에서의 최댓값을 구하면 됩니다. 이는 세그먼트 트리의 각 정점에서 CHT를 관리하는 것으로 처리할 수 있습니다.</p> <p>세그먼트 트리의 각 정점에 저장되는 직선의 기울기와 쿼리로 주어지는 x 좌표인 (-l + 1) 모두 단조성이 있으니 CHT를 선형에 처리할 수 있습니다.</p> <p>$T(N) = 2T(N/2) + O(N \log N)$이므로 $O(N \log^2 N)$에 문제를 풀 수 있습니다.</p> <h3 id="task-4-papričice-110점">Task 4. Papričice (110점)</h3> <h5 id="문제-3">문제</h5> <p>트리가 주어집니다. 트리의 간선을 2개 제거하면 3개의 컴포넌트로 나누어질텐데, 가장 큰 컴포넌트와 가장 작은 컴포넌트의 차이를 최소화하는 것이 이 문제의 목표입니다.</p> <p>N ≤ 200인 경우를 해결하면 15점, N ≤ 2000인 경우를 해결하면 35점, N ≤ 2e5인 경우를 해결하면 60점을 받아 총 110점 만점입니다.</p> <h5 id="풀이-3">풀이</h5> <p>풀이 설명과 구현의 편의를 위해 임의의 정점을 루트로 잡아서 rooted tree로 만듭시다.<br /> 제거하는 두 간선의 양 끝에 달린 정점 중 깊이 있는 정점을 각각 x, y라고 합시다.<br /> (1) x, y가 조상 관계인 경우와 (2) 그렇지 않은 경우, 2가지로 나누어서 생각합시다.</p> <p>1번 케이스를 먼저 봅시다. 일반성을 잃지 않고, x가 y의 조상이라고 합시다. 각 컴포넌트의 크기는 S[y], S[x] - S[y], N - S[x]가 됩니다.<br /> 2번 케이스에서 각 컴포넌트의 크기는 S[x], S[y], N - S[x] - S[y]가 됩니다.</p> <p>각 y에 대해서 적절한 x를 찾아 세 컴포넌트의 크기가 최대한 같아지도록 만들면 됩니다.<br /> 1번 케이스는 S[x]가 (N+S[y])/2에 가까워야하고, 2번 케이스는 S[x]가 (N-S[y])/2에 가까워야합니다.<br /> DFS를 돌면서, std::set에 lower_bound를 적당히 사용해주면 $O(N \log N)$만에 정답을 구할 수 있습니다.</p> <p><strong>“정답이 D 이하일 것이다.”</strong> 라고 파라메트릭 서치를 하면서 Persistent Segment Tree를 쓰면 $O(N \log^2 N)$, Merge Sort Tree를 쓰면 $O(N \log^3 N)$인데, 두 풀이 모두 TLE가 납니다. 개인적으로는 N ≤ 50000인 서브태스크가 있었으면 더 좋았을 것 같습니다.<br /> 이 코드도 아래에 같이 올리겠습니다.</p> <h3 id="task-5-tenis-110점">Task 5. Tenis (110점)</h3> <h5 id="문제-4">문제</h5> <p>N명의 선수가 풀리그 방식으로 테니스 경기를 합니다. 테니스 코트는 3가지 종류가 있고, 각 코트마다 참가자들의 순위가 주어집니다. 두 선수가 어떤 코트에서 경기를 한다면, 그 코트에서 순위가 높은 선수가 무조건 이깁니다.</p> <p>우리는 코트마다 참가자들의 순위가 주어졌을 때, 각 경기를 적절한 코트에서 진행해 최대한 <strong>좋은 경기</strong>가 되도록 만드려고 합니다.<br /> <strong>좋은 경기</strong>라는 것은, 경기의 승자가 가장 잘하는 코트에서 진행되는 경기를 의미합니다. (예를 들어 A 코트에서 경기를 했을 때 승자는 A 코트에서의 순위가 2등이고, B 코트에서 경기를 했을 때 승자는 B 코트에서의 순위가 1등이라면 B 코트에서 경기를 진행하는 것이 더 좋은 경기입니다.)<br /> 어떤 두 코트에서 승자의 순위가 똑같다면, 패자의 순위가 더 높은 것이 좋은 경기입니다. 승자와 패자 모두 순위가 같다면 더 작은 번호의 코트에서 진행하면 됩니다.</p> <p>N(N-1)/2번의 경기를 최대한 좋은 경기로 진행했을 때, 각 코트가 사용된 횟수와 각 선수가 이긴 횟수를 출력하면 됩니다.</p> <p>N ≤ 3000인 경우 50점을 받고, N ≤ 1e5인 경우 60점을 받습니다.</p> <h3 id="풀이-4">풀이</h3> <s>문제를 이해하는 것이 가장 어렵습니다.</s> <p>각 경기를 (1) 어떤 선수의 최대 순위가 다른 선수의 최대 순위보다 높은 경우와 (2) 그렇지 않은 경우, 총 2가지로 분류할 수 있습니다. 또한 2번 케이스는 최대 3N번 밖에 일어나지 않습니다. (두 선수 모두 최대 순위가 i인 경우는 최대 3가지 밖에 없습니다.)</p> <p>2번 케이스는 간단하게 처리할 수 있으니 1번 케이스만 설명하겠습니다. 2번 케이스에 대한 처리 방법이 궁금하면 아래 코드에서 go 함수를 참고하세요.</p> <p>1번 케이스를 해결하는 방법을 알아봅시다.<br /> 기본적인 접근 방법은, 각 사람에 대해 그 사람보다 잘하는 사람의 수(그 사람이 지는 경우의 수)를 구하는 것입니다.</p> <p>각 사람의 순위가 제일 높아지는 경기장을 비트로 표현합시다. 3비트로 표현되고, 공집합은 없기 때문에 7가지가 나옵니다. 순위가 제일 높은 경기장이 bit인 사람들의 최고 등수를 정렬해서 배열 vec[bit]에 저장합시다.<br /> vec[bit]에서 i번째 사람보다 잘하는 사람의 수는 이진탐색(std::lower_bound)를 이용해 쉽게 구할 수 있습니다. 어떤 코트에서 경기를 진행해야할지 결정만 하면 됩니다.</p> <p>승자는 비트가 켜져있는 코트에서 모두 동일한 퍼포먼스가 나오기 때문에 패자의 순위만 최소화하면 됩니다. 이것은 비트마스크를 이용해 간단하게 구현할 수 있습니다.</p> <h3 id="정답-코드">정답 코드</h3> <h5 id="task-1">Task 1</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">si</span><span class="p">,</span> <span class="n">sj</span><span class="p">;</span> <span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">111</span><span class="p">][</span><span class="mi">111</span><span class="p">];</span> <span class="kt">int</span> <span class="n">mn</span> <span class="o">=</span> <span class="mf">1e9</span><span class="p">;</span> <span class="kt">char</span> <span class="n">res</span><span class="p">;</span> <span class="kt">int</span> <span class="n">chk</span><span class="p">[</span><span class="mi">111</span><span class="p">][</span><span class="mi">111</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">go</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">,</span> <span class="kt">char</span> <span class="n">c</span><span class="p">){</span> <span class="n">memset</span><span class="p">(</span><span class="n">chk</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">chk</span><span class="p">);</span> <span class="kt">int</span> <span class="n">cnt</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="mi">1</span><span class="p">){</span> <span class="n">cnt</span><span class="o">++</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">++</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'.'</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'x'</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'&gt;'</span><span class="p">)</span> <span class="n">j</span><span class="o">++</span><span class="p">;</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'&lt;'</span><span class="p">)</span> <span class="n">j</span><span class="o">--</span><span class="p">;</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'^'</span><span class="p">)</span> <span class="n">i</span><span class="o">--</span><span class="p">;</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'v'</span><span class="p">)</span> <span class="n">i</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">mn</span> <span class="o">&gt;</span> <span class="n">cnt</span><span class="p">)</span> <span class="n">mn</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">res</span> <span class="o">=</span> <span class="n">c</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">){</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'o'</span><span class="p">)</span> <span class="n">si</span> <span class="o">=</span> <span class="n">i</span><span class="p">,</span> <span class="n">sj</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> <span class="p">}</span> <span class="n">go</span><span class="p">(</span><span class="n">si</span><span class="p">,</span> <span class="n">sj</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="sc">'E'</span><span class="p">);</span> <span class="n">go</span><span class="p">(</span><span class="n">si</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">sj</span><span class="p">,</span> <span class="sc">'N'</span><span class="p">);</span> <span class="n">go</span><span class="p">(</span><span class="n">si</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">sj</span><span class="p">,</span> <span class="sc">'S'</span><span class="p">);</span> <span class="n">go</span><span class="p">(</span><span class="n">si</span><span class="p">,</span> <span class="n">sj</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="sc">'W'</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">mn</span> <span class="o">==</span> <span class="mf">1e9</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">":("</span><span class="p">;</span> <span class="k">else</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">":)</span><span class="se">\n</span><span class="s">"</span> <span class="o">&lt;&lt;</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h5 id="task-2">Task 2</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">333</span><span class="p">],</span> <span class="n">b</span><span class="p">[</span><span class="mi">333</span><span class="p">];</span> <span class="n">ll</span> <span class="n">dp</span><span class="p">[</span><span class="mi">333</span><span class="p">][</span><span class="mi">333</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">memset</span><span class="p">(</span><span class="n">dp</span><span class="p">,</span> <span class="mh">0x3f</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">dp</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">b</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="n">dp</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">j</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">j</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+</span> <span class="n">abs</span><span class="p">(</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="o">-</span><span class="n">k</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+</span> <span class="n">abs</span><span class="p">(</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="o">-</span><span class="n">k</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">mn</span> <span class="o">=</span> <span class="mf">1e18</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">mn</span><span class="p">,</span> <span class="n">dp</span><span class="p">[</span><span class="n">m</span><span class="p">][</span><span class="n">i</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">mn</span> <span class="o">&gt;</span> <span class="mf">1e17</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="k">else</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">mn</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h5 id="task-3">Task 3</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="n">ll</span><span class="p">,</span> <span class="n">ll</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="n">ll</span> <span class="nf">ccw</span><span class="p">(</span><span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">,</span> <span class="k">const</span> <span class="n">p</span> <span class="o">&amp;</span><span class="n">c</span><span class="p">){</span> <span class="n">ll</span> <span class="n">dx1</span> <span class="o">=</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">a</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy1</span> <span class="o">=</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">a</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="n">ll</span> <span class="n">dx2</span> <span class="o">=</span> <span class="n">c</span><span class="p">.</span><span class="n">x</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">x</span><span class="p">,</span> <span class="n">dy2</span> <span class="o">=</span> <span class="n">c</span><span class="p">.</span><span class="n">y</span> <span class="o">-</span> <span class="n">b</span><span class="p">.</span><span class="n">y</span><span class="p">;</span> <span class="k">return</span> <span class="n">dx1</span><span class="o">*</span><span class="n">dy2</span> <span class="o">-</span> <span class="n">dx2</span><span class="o">*</span><span class="n">dy1</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">b</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">mx</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">tree</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">19</span><span class="p">];</span> <span class="n">p</span> <span class="n">val</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">int</span> <span class="n">pv</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">19</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">build</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">clear</span><span class="p">();</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">){</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">val</span><span class="p">[</span><span class="n">s</span><span class="p">]);</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="n">build</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> <span class="n">build</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">hull</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span><span class="p">];</span> <span class="n">hull</span> <span class="o">=</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]){</span> <span class="k">while</span><span class="p">(</span><span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">&gt;=</span> <span class="mi">2</span> <span class="o">&amp;&amp;</span> <span class="n">ccw</span><span class="p">(</span><span class="n">hull</span><span class="p">[</span><span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span><span class="o">-</span><span class="mi">2</span><span class="p">],</span> <span class="n">hull</span><span class="p">.</span><span class="n">back</span><span class="p">(),</span> <span class="n">i</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">hull</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span> <span class="n">hull</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="p">}</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">]</span> <span class="o">=</span> <span class="n">hull</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="kr">inline</span> <span class="n">ll</span> <span class="nf">f</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">idx</span><span class="p">,</span> <span class="n">ll</span> <span class="n">x</span><span class="p">){</span> <span class="k">return</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">x</span> <span class="o">*</span> <span class="n">x</span> <span class="o">+</span> <span class="n">tree</span><span class="p">[</span><span class="n">node</span><span class="p">][</span><span class="n">idx</span><span class="p">].</span><span class="n">y</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="n">ll</span> <span class="n">x</span><span class="p">){</span> <span class="k">while</span><span class="p">(</span><span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&gt;=</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">f</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">],</span> <span class="n">x</span><span class="p">)</span> <span class="o">&lt;=</span> <span class="n">f</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">x</span><span class="p">))</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">]</span><span class="o">--</span><span class="p">;</span> <span class="k">return</span> <span class="n">f</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">pv</span><span class="p">[</span><span class="n">node</span><span class="p">],</span> <span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="n">ll</span> <span class="n">x</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span> <span class="o">&lt;</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">s</span> <span class="o">&amp;&amp;</span> <span class="n">e</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="n">query</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">max</span><span class="p">(</span><span class="n">query</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">x</span><span class="p">),</span> <span class="n">query</span><span class="p">(</span><span class="n">node</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">x</span><span class="p">));</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">calc1</span><span class="p">(</span><span class="kt">int</span> <span class="n">st</span><span class="p">,</span> <span class="kt">int</span> <span class="n">md</span><span class="p">,</span> <span class="kt">int</span> <span class="n">ed</span><span class="p">){</span> <span class="n">ll</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">md</span><span class="p">],</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">b</span><span class="p">[</span><span class="n">md</span><span class="p">];</span> <span class="kt">int</span> <span class="n">pv</span> <span class="o">=</span> <span class="n">md</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">md</span><span class="p">;</span> <span class="n">i</span><span class="o">&gt;=</span><span class="n">st</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">){</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">a_mn</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">b_mn</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">while</span><span class="p">(</span><span class="n">pv</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">ed</span> <span class="o">&amp;&amp;</span> <span class="n">a_mn</span> <span class="o">&lt;=</span> <span class="n">a</span><span class="p">[</span><span class="n">pv</span><span class="o">+</span><span class="mi">1</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">b_mn</span> <span class="o">&lt;=</span> <span class="n">b</span><span class="p">[</span><span class="n">pv</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">,</span> <span class="n">a_mn</span> <span class="o">*</span> <span class="n">b_mn</span> <span class="o">*</span> <span class="p">(</span><span class="n">pv</span> <span class="o">-</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">));</span> <span class="p">}</span> <span class="p">}</span> <span class="n">p</span> <span class="n">range</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">calc2</span><span class="p">(</span><span class="kt">int</span> <span class="n">st</span><span class="p">,</span> <span class="kt">int</span> <span class="n">md</span><span class="p">,</span> <span class="kt">int</span> <span class="n">ed</span><span class="p">){</span> <span class="n">ll</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">md</span><span class="p">],</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">b</span><span class="p">[</span><span class="n">md</span><span class="p">];</span> <span class="kt">int</span> <span class="n">s</span> <span class="o">=</span> <span class="n">md</span><span class="p">,</span> <span class="n">e</span> <span class="o">=</span> <span class="n">md</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">md</span><span class="p">;</span> <span class="n">i</span><span class="o">&gt;=</span><span class="n">st</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">){</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">a_mn</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">b_mn</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">while</span><span class="p">(</span><span class="n">e</span> <span class="o">&lt;</span> <span class="n">ed</span> <span class="o">&amp;&amp;</span> <span class="n">a_mn</span> <span class="o">&lt;=</span> <span class="n">a</span><span class="p">[</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span> <span class="n">e</span><span class="o">++</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">s</span> <span class="o">&lt;=</span> <span class="n">ed</span> <span class="o">&amp;&amp;</span> <span class="n">b_mn</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">[</span><span class="n">s</span><span class="p">])</span> <span class="n">s</span><span class="o">++</span><span class="p">;</span> <span class="n">range</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="p">}</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">b</span><span class="p">[</span><span class="n">md</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">md</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">ed</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">b_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">b_mn</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">val</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">(</span><span class="n">b_mn</span><span class="p">,</span> <span class="n">i</span> <span class="o">*</span> <span class="n">b_mn</span><span class="p">);</span> <span class="p">}</span> <span class="n">build</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">md</span><span class="p">,</span> <span class="n">ed</span><span class="p">);</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">md</span><span class="p">];</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">md</span><span class="p">;</span> <span class="n">i</span><span class="o">&gt;=</span><span class="n">st</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">){</span> <span class="n">a_mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">a_mn</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">ll</span> <span class="n">t</span> <span class="o">=</span> <span class="n">a_mn</span> <span class="o">*</span> <span class="n">query</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">md</span><span class="p">,</span> <span class="n">ed</span><span class="p">,</span> <span class="n">range</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="n">range</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">y</span><span class="p">,</span> <span class="o">-</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">dnc</span><span class="p">(</span><span class="kt">int</span> <span class="n">st</span><span class="p">,</span> <span class="kt">int</span> <span class="n">ed</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">st</span> <span class="o">&gt;</span> <span class="n">ed</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">st</span> <span class="o">==</span> <span class="n">ed</span><span class="p">){</span> <span class="n">mx</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">mx</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">st</span><span class="p">]</span> <span class="o">*</span> <span class="n">b</span><span class="p">[</span><span class="n">st</span><span class="p">]);</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">md</span> <span class="o">=</span> <span class="n">st</span> <span class="o">+</span> <span class="n">ed</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="n">calc1</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">md</span><span class="p">,</span> <span class="n">ed</span><span class="p">);</span> <span class="n">calc2</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">md</span><span class="p">,</span> <span class="n">ed</span><span class="p">);</span> <span class="n">dnc</span><span class="p">(</span><span class="n">st</span><span class="p">,</span> <span class="n">md</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">dnc</span><span class="p">(</span><span class="n">md</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">ed</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">rev</span><span class="p">(){</span> <span class="n">reverse</span><span class="p">(</span><span class="n">a</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">a</span><span class="o">+</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="n">reverse</span><span class="p">(</span><span class="n">b</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">b</span><span class="o">+</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">swp</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">dnc</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="n">swp</span><span class="p">();</span> <span class="n">dnc</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="n">rev</span><span class="p">();</span> <span class="n">dnc</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="n">swp</span><span class="p">();</span> <span class="n">dnc</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">mx</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h5 id="task-4">Task 4</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">sz</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">mn</span> <span class="o">=</span> <span class="mf">1e9</span><span class="o">+</span><span class="mi">7</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="n">multiset</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">in</span><span class="p">,</span> <span class="n">out</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">b</span><span class="p">)</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="p">}</span> <span class="kr">inline</span> <span class="kt">void</span> <span class="nf">f</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">,</span> <span class="kt">int</span> <span class="n">c</span><span class="p">){</span> <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">})</span> <span class="o">-</span> <span class="n">min</span><span class="p">({</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">});</span> <span class="n">mn</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">mn</span><span class="p">,</span> <span class="n">t</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">){</span> <span class="k">auto</span> <span class="n">it1</span> <span class="o">=</span> <span class="n">in</span><span class="p">.</span><span class="n">lower_bound</span><span class="p">((</span><span class="n">n</span><span class="o">+</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">])</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">it1</span> <span class="o">!=</span> <span class="n">in</span><span class="p">.</span><span class="n">end</span><span class="p">())</span> <span class="n">f</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="o">*</span><span class="n">it1</span><span class="o">-</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="n">n</span><span class="o">-*</span><span class="n">it1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">it1</span> <span class="o">!=</span> <span class="n">in</span><span class="p">.</span><span class="n">begin</span><span class="p">())</span> <span class="o">--</span><span class="n">it1</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="o">*</span><span class="n">it1</span><span class="o">-</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="n">n</span><span class="o">-*</span><span class="n">it1</span><span class="p">);</span> <span class="k">auto</span> <span class="n">it2</span> <span class="o">=</span> <span class="n">out</span><span class="p">.</span><span class="n">lower_bound</span><span class="p">((</span><span class="n">n</span><span class="o">-</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">])</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">it2</span> <span class="o">!=</span> <span class="n">out</span><span class="p">.</span><span class="n">end</span><span class="p">())</span> <span class="n">f</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="o">*</span><span class="n">it2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">-*</span><span class="n">it2</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">it2</span> <span class="o">!=</span> <span class="n">out</span><span class="p">.</span><span class="n">begin</span><span class="p">())</span> <span class="o">--</span><span class="n">it2</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">],</span> <span class="o">*</span><span class="n">it2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span><span class="o">-*</span><span class="n">it2</span><span class="p">);</span> <span class="n">in</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">b</span><span class="p">)</span> <span class="n">solve</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="n">in</span><span class="p">.</span><span class="n">erase</span><span class="p">(</span><span class="n">in</span><span class="p">.</span><span class="n">find</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]));</span> <span class="n">out</span><span class="p">.</span><span class="n">insert</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">solve</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">mn</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h5 id="task-5">Task 5</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) lower_bound(all(v), x) - v.begin() </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">3</span><span class="p">][</span><span class="mi">101010</span><span class="p">],</span> <span class="n">rnk</span><span class="p">[</span><span class="mi">3</span><span class="p">][</span><span class="mi">101010</span><span class="p">],</span> <span class="n">mn</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">vec</span><span class="p">[</span><span class="mi">8</span><span class="p">];</span> <span class="n">ll</span> <span class="n">cnt</span><span class="p">[</span><span class="mi">3</span><span class="p">],</span> <span class="n">lose</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="n">set</span><span class="o">&lt;</span><span class="n">p</span><span class="o">&gt;</span> <span class="n">st</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">go</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">y</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span> <span class="o">==</span> <span class="n">y</span> <span class="o">||</span> <span class="n">st</span><span class="p">.</span><span class="n">count</span><span class="p">(</span><span class="n">p</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">)))</span> <span class="k">return</span><span class="p">;</span> <span class="n">st</span><span class="p">.</span><span class="n">emplace</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">);</span> <span class="n">p</span> <span class="n">t</span><span class="p">[</span><span class="mi">3</span><span class="p">];</span> <span class="kt">int</span> <span class="n">flag</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">){</span> <span class="n">t</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">x</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">y</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">t</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">y</span><span class="p">)</span> <span class="n">swap</span><span class="p">(</span><span class="n">t</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">x</span><span class="p">,</span> <span class="n">t</span><span class="p">[</span><span class="n">k</span><span class="p">].</span><span class="n">y</span><span class="p">),</span> <span class="n">flag</span><span class="p">[</span><span class="n">k</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">min_element</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">t</span><span class="o">+</span><span class="mi">3</span><span class="p">)</span> <span class="o">-</span> <span class="n">t</span><span class="p">;</span> <span class="n">cnt</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="p">(</span><span class="n">flag</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">?</span> <span class="n">lose</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">:</span> <span class="n">lose</span><span class="p">[</span><span class="n">y</span><span class="p">])</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">rnk</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">rnk</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]]</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">mn</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">({</span> <span class="n">a</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">][</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="p">});</span> <span class="kt">int</span> <span class="n">bit</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">mn</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">bit</span> <span class="o">|=</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">);</span> <span class="n">vec</span><span class="p">[</span><span class="n">bit</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">mn</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">8</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">vec</span><span class="p">[</span><span class="n">i</span><span class="p">]));</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">rnk</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">],</span> <span class="n">y</span> <span class="o">=</span> <span class="n">rnk</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">i</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">mn</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">i</span> <span class="o">&amp;&amp;</span> <span class="n">mn</span><span class="p">[</span><span class="n">y</span><span class="p">]</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="n">go</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">);</span> <span class="p">}</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">bit</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">bit</span><span class="o">&lt;</span><span class="mi">8</span><span class="p">;</span> <span class="n">bit</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">val</span> <span class="o">=</span> <span class="n">IDX</span><span class="p">(</span><span class="n">vec</span><span class="p">[</span><span class="n">bit</span><span class="p">],</span> <span class="n">mn</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span> <span class="n">court</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">bit</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">))</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">court</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span> <span class="o">||</span> <span class="n">a</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">a</span><span class="p">[</span><span class="n">court</span><span class="p">][</span><span class="n">i</span><span class="p">])</span> <span class="n">court</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> <span class="p">}</span> <span class="n">cnt</span><span class="p">[</span><span class="n">court</span><span class="p">]</span> <span class="o">+=</span> <span class="n">val</span><span class="p">;</span> <span class="n">lose</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">val</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="mi">3</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="o">-</span><span class="n">lose</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h3 id="부분-점수-코드">부분 점수 코드</h3> <h5 id="task-4---on-log3-n-with-merge-sort-tree">Task 4 - O(N log^3 N) with Merge Sort Tree</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">18</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">in</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">out</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">sz</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">pv</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">in</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">b</span><span class="p">)</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="n">out</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">pv</span><span class="p">;</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="p">}</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">tree</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">19</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">build</span><span class="p">(){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">in</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">|</span><span class="n">S</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">S</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="n">merge</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">]),</span> <span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">i</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]),</span> <span class="n">back_inserter</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">i</span><span class="p">]));</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t2</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">t1</span> <span class="o">&gt;</span> <span class="n">t2</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="n">l</span> <span class="o">|=</span> <span class="n">S</span><span class="p">;</span> <span class="n">r</span> <span class="o">|=</span> <span class="n">S</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">ret</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">){</span> <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">upper_bound</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">l</span><span class="p">]),</span> <span class="n">t2</span><span class="p">)</span> <span class="o">-</span> <span class="n">lower_bound</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">l</span><span class="p">]),</span> <span class="n">t1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="n">l</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="o">~</span><span class="n">r</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">){</span> <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">upper_bound</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">r</span><span class="p">]),</span> <span class="n">t2</span><span class="p">)</span> <span class="o">-</span> <span class="n">lower_bound</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">r</span><span class="p">]),</span> <span class="n">t1</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="n">r</span><span class="o">--</span><span class="p">;</span> <span class="p">}</span> <span class="n">l</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">r</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">chk</span><span class="p">(</span><span class="kt">int</span> <span class="n">d</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">d</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">});</span> <span class="n">r</span> <span class="o">=</span> <span class="n">min</span><span class="p">({</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="n">n</span><span class="o">+</span><span class="n">d</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">});</span> <span class="k">if</span><span class="p">(</span><span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">query</span><span class="p">(</span><span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">))</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">max</span><span class="p">({(</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="p">,</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">n</span><span class="o">-</span><span class="n">d</span><span class="p">});</span> <span class="n">r</span> <span class="o">=</span> <span class="n">min</span><span class="p">({(</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">n</span><span class="o">+</span><span class="n">d</span><span class="p">});</span> <span class="k">if</span><span class="p">(</span><span class="n">in</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">query</span><span class="p">(</span><span class="n">in</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">))</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">build</span><span class="p">();</span> <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">){</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">l</span> <span class="o">+</span> <span class="n">r</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">(</span><span class="n">m</span><span class="p">))</span> <span class="n">r</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="k">else</span> <span class="n">l</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">r</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <h5 id="task-4---on-log2-n-with-persistent-segment-tree">Task 4 - O(N log^2 N) with Persistent Segment Tree</h5> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#pragma GCC optimize ("O3") #include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">S</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">18</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">in</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">out</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">sz</span><span class="p">[</span><span class="mi">202020</span><span class="p">],</span> <span class="n">pv</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">g</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">dfs</span><span class="p">(</span><span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">in</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="o">++</span><span class="n">pv</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="k">auto</span> <span class="n">i</span> <span class="o">:</span> <span class="n">g</span><span class="p">[</span><span class="n">v</span><span class="p">])</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">b</span><span class="p">)</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">+=</span> <span class="n">dfs</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span> <span class="n">out</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">pv</span><span class="p">;</span> <span class="k">return</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">];</span> <span class="p">}</span> <span class="k">struct</span> <span class="nc">Node</span><span class="p">{</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">,</span> <span class="n">v</span><span class="p">;</span> <span class="n">Node</span><span class="p">(){</span> <span class="n">l</span> <span class="o">=</span> <span class="n">r</span> <span class="o">=</span> <span class="n">v</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="p">};</span> <span class="k">struct</span> <span class="nc">PST</span><span class="p">{</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">pv</span><span class="p">,</span> <span class="n">root</span><span class="p">[</span><span class="mi">202020</span><span class="p">];</span> <span class="n">Node</span> <span class="n">nd</span><span class="p">[</span><span class="mi">5050505</span><span class="p">];</span> <span class="n">PST</span><span class="p">(</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span> <span class="o">:</span> <span class="n">n</span><span class="p">(</span><span class="n">n</span><span class="p">)</span> <span class="p">{</span> <span class="n">memset</span><span class="p">(</span><span class="n">root</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span> <span class="n">root</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">init</span><span class="p">(</span><span class="kt">int</span> <span class="n">node</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">l</span><span class="p">)</span> <span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">l</span> <span class="o">=</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">r</span><span class="p">)</span> <span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">r</span> <span class="o">=</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="n">init</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">l</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> <span class="n">init</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">node</span><span class="p">].</span><span class="n">r</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">init</span><span class="p">(){</span> <span class="n">pv</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="n">init</span><span class="p">(</span><span class="n">root</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="n">update</span><span class="p">(</span><span class="kt">int</span> <span class="n">prv</span><span class="p">,</span> <span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">s</span> <span class="o">==</span> <span class="n">e</span><span class="p">){</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">v</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">prv</span><span class="p">].</span><span class="n">v</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;=</span> <span class="n">m</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span><span class="p">)</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span> <span class="o">=</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">prv</span><span class="p">].</span><span class="n">r</span><span class="p">;</span> <span class="n">update</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">prv</span><span class="p">].</span><span class="n">l</span><span class="p">,</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="k">else</span><span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span><span class="p">)</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span> <span class="o">=</span> <span class="n">pv</span><span class="o">++</span><span class="p">;</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">prv</span><span class="p">].</span><span class="n">l</span><span class="p">;</span> <span class="n">update</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">prv</span><span class="p">].</span><span class="n">r</span><span class="p">,</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">x</span><span class="p">);</span> <span class="p">}</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">v</span> <span class="o">=</span> <span class="n">nd</span><span class="p">[</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span><span class="p">].</span><span class="n">v</span> <span class="o">+</span> <span class="n">nd</span><span class="p">[</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span><span class="p">].</span><span class="n">v</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">now</span><span class="p">,</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">r</span> <span class="o">&lt;</span> <span class="n">s</span> <span class="o">||</span> <span class="n">e</span> <span class="o">&lt;</span> <span class="n">l</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">s</span> <span class="o">&amp;&amp;</span> <span class="n">e</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">)</span> <span class="k">return</span> <span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">v</span><span class="p">;</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">return</span> <span class="n">query</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">l</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span> <span class="o">+</span> <span class="n">query</span><span class="p">(</span><span class="n">nd</span><span class="p">[</span><span class="n">now</span><span class="p">].</span><span class="n">r</span><span class="p">,</span> <span class="n">m</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">e</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">);</span> <span class="p">}</span> <span class="p">};</span> <span class="kt">void</span> <span class="nf">build</span><span class="p">(</span><span class="n">PST</span> <span class="o">&amp;</span><span class="n">tree</span><span class="p">){</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">v</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="n">iota</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">v</span><span class="p">),</span> <span class="mi">1</span><span class="p">);</span> <span class="n">sort</span><span class="p">(</span><span class="n">all</span><span class="p">(</span><span class="n">v</span><span class="p">),</span> <span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">){</span> <span class="k">return</span> <span class="n">in</span><span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">in</span><span class="p">[</span><span class="n">b</span><span class="p">];</span> <span class="p">});</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">tree</span><span class="p">.</span><span class="n">update</span><span class="p">(</span><span class="n">tree</span><span class="p">.</span><span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="n">tree</span><span class="p">.</span><span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">sz</span><span class="p">[</span><span class="n">v</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]]);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">query</span><span class="p">(</span><span class="n">PST</span> <span class="o">&amp;</span><span class="n">tree</span><span class="p">,</span> <span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">t2</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&gt;</span> <span class="n">r</span> <span class="o">||</span> <span class="n">t1</span> <span class="o">&gt;</span> <span class="n">t2</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="kt">int</span> <span class="n">X</span> <span class="o">=</span> <span class="n">tree</span><span class="p">.</span><span class="n">query</span><span class="p">(</span><span class="n">tree</span><span class="p">.</span><span class="n">root</span><span class="p">[</span><span class="n">r</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">);</span> <span class="kt">int</span> <span class="n">Y</span> <span class="o">=</span> <span class="n">tree</span><span class="p">.</span><span class="n">query</span><span class="p">(</span><span class="n">tree</span><span class="p">.</span><span class="n">root</span><span class="p">[</span><span class="n">l</span><span class="o">-</span><span class="mi">1</span><span class="p">],</span> <span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">t1</span><span class="p">,</span> <span class="n">t2</span><span class="p">);</span> <span class="k">return</span> <span class="n">X</span><span class="o">-</span><span class="n">Y</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">chk</span><span class="p">(</span><span class="n">PST</span> <span class="o">&amp;</span><span class="n">tree</span><span class="p">,</span> <span class="kt">int</span> <span class="n">d</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">max</span><span class="p">({</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">d</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">});</span> <span class="n">r</span> <span class="o">=</span> <span class="n">min</span><span class="p">({</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="n">n</span><span class="o">+</span><span class="n">d</span><span class="o">-</span><span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">});</span> <span class="k">if</span><span class="p">(</span><span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">query</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">n</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">))</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="n">l</span> <span class="o">=</span> <span class="n">max</span><span class="p">({(</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">-</span><span class="n">d</span><span class="p">,</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">n</span><span class="o">-</span><span class="n">d</span><span class="p">});</span> <span class="n">r</span> <span class="o">=</span> <span class="n">min</span><span class="p">({(</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span><span class="o">-</span><span class="n">x</span><span class="o">+</span><span class="n">d</span><span class="p">,</span> <span class="mi">2</span><span class="o">*</span><span class="n">x</span><span class="o">-</span><span class="n">n</span><span class="o">+</span><span class="n">d</span><span class="p">});</span> <span class="k">if</span><span class="p">(</span><span class="n">in</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span> <span class="o">&lt;=</span> <span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&amp;&amp;</span> <span class="n">query</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">in</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">out</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">))</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">PST</span> <span class="n">pst</span><span class="p">(</span><span class="n">n</span><span class="p">);</span> <span class="n">pst</span><span class="p">.</span><span class="n">init</span><span class="p">();</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">e</span><span class="p">);</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">].</span><span class="n">push_back</span><span class="p">(</span><span class="n">s</span><span class="p">);</span> <span class="p">}</span> <span class="n">dfs</span><span class="p">(</span><span class="mi">1</span><span class="p">);</span> <span class="n">build</span><span class="p">(</span><span class="n">pst</span><span class="p">);</span> <span class="kt">int</span> <span class="n">l</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">r</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">){</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">l</span> <span class="o">+</span> <span class="n">r</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">(</span><span class="n">pst</span><span class="p">,</span> <span class="n">m</span><span class="p">))</span> <span class="n">r</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="k">else</span> <span class="n">l</span> <span class="o">=</span> <span class="n">m</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">r</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHuiOverview 3시간 5문제 셋입니다. 앞쪽 2문제는 난이도순, 나머지 3문제는 난이도 상관 없이 섞어놓은 것 같습니다.백준16214 N과 M2020-10-22T04:14:00+00:002020-10-22T04:14:00+00:00https://justicehui.github.io/ps/2020/10/22/BOJ16214<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/16214</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>오일러 파이 함수</li> </ul> <h3 id="풀이">풀이</h3> <p>a와 m이 서로소라면 $a^n \equiv a^{n \mod \phi(m)} \mod m$입니다.<br /> 따라서 문제의 정답을 $f(n, m)$이라고 하면, n과 m이 서로소일 때 $f(n, m) \equiv n^{f(n, \phi(m))} \mod m$입니다.</p> <p>서로소가 아닌 경우가 문제인데, n이 작은 경우에 naive하게 계산해주니 AC가 나왔습니다. 왜 되는지는 모르겠네요.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="n">ll</span> <span class="nf">phi</span><span class="p">(</span><span class="n">ll</span> <span class="n">n</span><span class="p">){</span> <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="n">ll</span> <span class="n">p</span> <span class="o">=</span> <span class="mi">2</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">p</span><span class="o">*</span><span class="n">p</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="n">p</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">ret</span> <span class="o">/</span> <span class="n">p</span> <span class="o">*</span> <span class="p">(</span><span class="n">p</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span> <span class="k">while</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="n">p</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="n">n</span> <span class="o">/=</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">!=</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">ret</span> <span class="o">/</span> <span class="n">n</span> <span class="o">*</span> <span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">);</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">pw</span><span class="p">(</span><span class="n">ll</span> <span class="n">a</span><span class="p">,</span> <span class="n">ll</span> <span class="n">b</span><span class="p">,</span> <span class="n">ll</span> <span class="n">c</span><span class="p">){</span> <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">ret</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">c</span><span class="p">;</span> <span class="n">b</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">a</span> <span class="o">=</span> <span class="n">a</span> <span class="o">*</span> <span class="n">a</span> <span class="o">%</span> <span class="n">c</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">__int128_t</span> <span class="nf">pw</span><span class="p">(</span><span class="n">__int128_t</span> <span class="n">a</span><span class="p">,</span> <span class="n">__int128_t</span> <span class="n">b</span><span class="p">){</span> <span class="n">__int128_t</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">b</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">b</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">*=</span> <span class="n">a</span><span class="p">;</span> <span class="n">b</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">a</span> <span class="o">*=</span> <span class="n">a</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">naive</span><span class="p">(</span><span class="n">__int128_t</span> <span class="n">n</span><span class="p">,</span> <span class="n">__int128_t</span> <span class="n">m</span><span class="p">){</span> <span class="n">ll</span> <span class="n">prv</span> <span class="o">=</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">ll</span> <span class="n">real</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">n</span> <span class="o">=</span> <span class="n">pw</span><span class="p">(</span><span class="n">real</span><span class="p">,</span> <span class="n">n</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">prv</span> <span class="o">==</span> <span class="n">n</span> <span class="o">%</span> <span class="n">m</span><span class="p">)</span> <span class="k">return</span> <span class="n">prv</span><span class="p">;</span> <span class="n">prv</span> <span class="o">=</span> <span class="n">n</span> <span class="o">%</span> <span class="n">m</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">f</span><span class="p">(</span><span class="n">ll</span> <span class="n">n</span><span class="p">,</span> <span class="n">ll</span> <span class="n">m</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">m</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">&lt;=</span> <span class="mi">5</span><span class="p">)</span> <span class="k">return</span> <span class="n">naive</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">);</span> <span class="k">return</span> <span class="n">pw</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">phi</span><span class="p">(</span><span class="n">m</span><span class="p">))</span> <span class="o">+</span> <span class="n">phi</span><span class="p">(</span><span class="n">m</span><span class="p">),</span> <span class="n">m</span><span class="p">);</span> <span class="p">}</span> <span class="kt">void</span> <span class="nf">solve</span><span class="p">(){</span> <span class="n">ll</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">f</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">)</span> <span class="o">%</span> <span class="n">m</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="kt">int</span> <span class="n">t</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">t</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">)</span> <span class="n">solve</span><span class="p">();</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/16214백준20052 괄호 문자열 ?2020-10-21T04:11:00+00:002020-10-21T04:11:00+00:00https://justicehui.github.io/ps/2020/10/21/BOJ20052<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/20052</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>세그먼트 트리</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(Q \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>어떤 부분 문자열이 valid한 괄호 문자열이라는 것은</p> <ul> <li>여는 괄호를 1, 닫는 괄호를 -1로 치환했을 때 구간의 합이 0이고</li> <li>구간의 Prefix Sum의 최솟값이 0 이상인 경우를 의미합니다.</li> </ul> <p>세그먼트 트리를 이용해 문제를 풀 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">tree</span><span class="p">[</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">18</span><span class="p">];</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">sz</span> <span class="o">=</span> <span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="mi">17</span><span class="p">;</span> <span class="kt">void</span> <span class="nf">update</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">){</span> <span class="n">x</span> <span class="o">|=</span> <span class="n">sz</span><span class="p">;</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">tree</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span><span class="p">],</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span> <span class="o">&lt;&lt;</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">1</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">){</span> <span class="n">l</span> <span class="o">|=</span> <span class="n">sz</span><span class="p">;</span> <span class="n">r</span> <span class="o">|=</span> <span class="n">sz</span><span class="p">;</span> <span class="kt">int</span> <span class="n">ret</span> <span class="o">=</span> <span class="mf">1e9</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">l</span> <span class="o">&lt;=</span> <span class="n">r</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">l</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">tree</span><span class="p">[</span><span class="n">l</span><span class="o">++</span><span class="p">]);</span> <span class="k">if</span><span class="p">(</span><span class="o">~</span><span class="n">r</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">ret</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">ret</span><span class="p">,</span> <span class="n">tree</span><span class="p">[</span><span class="n">r</span><span class="o">--</span><span class="p">]);</span> <span class="n">l</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">r</span> <span class="o">&gt;&gt;=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">q</span><span class="p">;</span> <span class="n">string</span> <span class="n">s</span><span class="p">;</span> <span class="kt">int</span> <span class="n">a</span><span class="p">[</span><span class="mi">101010</span><span class="p">],</span> <span class="n">sum</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">q</span><span class="p">;</span> <span class="n">n</span> <span class="o">=</span> <span class="n">s</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">s</span> <span class="o">=</span> <span class="s">"#"</span> <span class="o">+</span> <span class="n">s</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="sc">'('</span> <span class="o">?</span> <span class="mi">1</span> <span class="o">:</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span> <span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">update</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">sum</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">ans</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">q</span><span class="o">--</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="kt">int</span> <span class="n">mn</span> <span class="o">=</span> <span class="n">query</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">)</span> <span class="o">-</span> <span class="n">sum</span><span class="p">[</span><span class="n">s</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">sum</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">-</span> <span class="n">sum</span><span class="p">[</span><span class="n">s</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">mn</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">ans</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/20052백준2802 크레용2020-10-20T04:04:00+00:002020-10-20T04:04:00+00:00https://justicehui.github.io/coci/2020/10/20/BOJ2802<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/2802</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2011/2012 COCI Contest #6 5번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>누적합</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N + 256^3 \log 256)$</li> </ul> <h3 id="풀이">풀이</h3> <p>어떤 값을 최소화하는 문제이니 <strong>정답이 $T$ 이하인지 판별하는</strong> 파라메트릭 서치를 생각해볼 수 있습니다.</p> <p>각 크레용을 3차원 좌표 공간 상에서 $(r_i, g_i, b_i)$ 꼴의 점으로 표현할 수 있습니다.<br /> 어떤 점 $(x, y, z)$가 있어서, $(x, y, z)$부터 $(x+T-1, y+T-1, z+T-1)$까지의 공간에 $K$개 이상의 점이 판별할 수 있으면 됩니다. 이 결정 문제는 3차원 누적 합을 이용해 $O(256^3)$에 해결할 수 있고, 따라서 전체 문제를 $O(N + 256^3 \log 256)$에 문제를 풀 수 있습니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="mi">256</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">k</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">333</span><span class="p">][</span><span class="mi">333</span><span class="p">][</span><span class="mi">333</span><span class="p">];</span> <span class="kt">int</span> <span class="n">r</span><span class="p">[</span><span class="mi">101010</span><span class="p">],</span> <span class="n">g</span><span class="p">[</span><span class="mi">101010</span><span class="p">],</span> <span class="n">b</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="n">xx</span><span class="p">,</span> <span class="kt">int</span> <span class="n">y</span><span class="p">,</span> <span class="kt">int</span> <span class="n">yy</span><span class="p">,</span> <span class="kt">int</span> <span class="n">z</span><span class="p">,</span> <span class="kt">int</span> <span class="n">zz</span><span class="p">){</span> <span class="kt">int</span> <span class="n">res</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">xx</span><span class="p">][</span><span class="n">yy</span><span class="p">][</span><span class="n">zz</span><span class="p">];</span> <span class="n">res</span> <span class="o">-=</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">yy</span><span class="p">][</span><span class="n">zz</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">xx</span><span class="p">][</span><span class="n">y</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">zz</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">xx</span><span class="p">][</span><span class="n">yy</span><span class="p">][</span><span class="n">z</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="n">res</span> <span class="o">+=</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">y</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">zz</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">yy</span><span class="p">][</span><span class="n">z</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">xx</span><span class="p">][</span><span class="n">y</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">z</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="n">res</span> <span class="o">-=</span> <span class="n">a</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">y</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">z</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="k">return</span> <span class="n">res</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">chk</span><span class="p">(</span><span class="kt">int</span> <span class="n">d</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">y</span><span class="p">,</span> <span class="kt">int</span> <span class="o">&amp;</span><span class="n">z</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">d</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">d</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">d</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">query</span><span class="p">(</span><span class="n">i</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">k</span><span class="o">-</span><span class="n">d</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">k</span><span class="p">);</span> <span class="k">if</span><span class="p">(</span><span class="n">t</span> <span class="o">&gt;=</span> <span class="o">::</span><span class="n">k</span><span class="p">){</span> <span class="n">x</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="n">y</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span> <span class="n">z</span> <span class="o">=</span> <span class="n">k</span><span class="p">;</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">k</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;&gt;</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="o">++</span><span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="o">++</span><span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]][</span><span class="o">++</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;=</span><span class="n">m</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">){</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">-=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]</span> <span class="o">+=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">s</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="n">e</span> <span class="o">=</span> <span class="n">m</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">;</span> <span class="k">while</span><span class="p">(</span><span class="n">s</span> <span class="o">&lt;</span> <span class="n">e</span><span class="p">){</span> <span class="kt">int</span> <span class="n">md</span> <span class="o">=</span> <span class="n">s</span> <span class="o">+</span> <span class="n">e</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">(</span><span class="n">md</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">))</span> <span class="n">e</span> <span class="o">=</span> <span class="n">md</span><span class="p">;</span> <span class="k">else</span> <span class="n">s</span> <span class="o">=</span> <span class="n">md</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="n">chk</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">z</span><span class="p">);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">e</span><span class="o">-</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span> <span class="o">&lt;</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">||</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">x</span><span class="o">-</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">y</span> <span class="o">&lt;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">||</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">y</span><span class="o">-</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">z</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">||</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">z</span><span class="o">-</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="k">continue</span><span class="p">;</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">r</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span> <span class="o">&lt;&lt;</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span> <span class="o">&lt;&lt;</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span> <span class="n">k</span><span class="o">--</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/2802백준17643 Amusement Park2020-10-19T03:20:00+00:002020-10-19T03:20:00+00:00https://justicehui.github.io/ceoi/2020/10/19/BOJ17643<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/17643</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2019 CEOI Day2 1번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>DP</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(3^N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>주어진 간선으로 만들 수 있는 모든 DAG의 가중치의 합을 구하는 문제입니다.<br /> DAG의 가중치는 각 간선의 가중치의 합으로 정의되고, 간선의 가중치는 입력으로 주어진대로 사용하면 0, 반대 방향으로 사용하면 1입니다.</p> <h5 id="subtask-4-63점-n--15">Subtask 4 (63점, N ≤ 15)</h5> <p>DAG의 위상정렬은 유일하지 않을 수 있으니 유일한 순서를 정의하는 것이 편할 것 같습니다.<br /> $ord(G)$ = Kahn’s Algorithm(BFS로 위상정렬하는 방법)의 각 단계에서, 선택할 수 있는 가장 작은 정점을 선택해서 얻은 순서로 정의합시다. 이렇게 정의하면 각 DAG $G$는 유일한 $ord(G)$를 갖습니다.</p> <p>$D(A, B)$ = $ord(G)$의 prefix가 $A$의 순열이고, indegree가 0인 정점이 $B$인 DAG의 개수로 정의하면, 상태공간이 $O(4^N)$가지인 DP가 나옵니다.<br /> 상태전이는 $A$에 정점 $c$를 추가하는 것으로 생각하면 됩니다.<br /> 시간복잡도는 $O(N 4^N)$이지만, 실제로는 불가능한 상태가 꽤 많기 때문에 $N \leq 15$면 시간 내에 구할 수 있습니다.</p> <p>어떤 순열 $P$가 DAG가 될 수 있다면 그 순열을 뒤집은(모든 간선의 방향을 뒤집은) $P^R$도 가능합니다. 그러므로 문제의 정답은 (DAG 경우의 수) × $\frac{M}{2}$입니다.<br /> <a href="https://oj.uz/submission/313775">코드</a></p> <h5 id="subtask-5-100점-n--18">Subtask 5 (100점, N ≤ 18)</h5> <p>위 풀이에서 $A$와 $B$가 disjoint함을 관찰하고 3진법을 사용하면 $O(N 3^N)$에 풀 수 있다는데 저는 구현을 못해서 다른 풀이를 짰습니다.</p> <p>$D(i)$ = 집합 $i$에 있는 정점들로만 DAG를 만드는 경우의 수로 정의합시다.</p> <p>DAG에는 indegree가 0인 정점이 몇 개 존재합니다.<br /> $i$의 부분집합 $j$에 대해 $j$에 있는 모든 정점의 indegree가 0이라고 고정하면, $i \setminus j$로 만든 DAG에 $j$의 원소들을 붙여서 새로운 DAG를 만들 수 있습니다.<br /> 포함배제를 이용하면 $\displaystyle D(i) = \sum_{j \subset i, j \neq \emptyset} (-1)^{\vert j \vert + 1}dp[i \oplus j]$라는 점화식을 찾을 수 있습니다.</p> <p>시간 복잡도는 $\displaystyle \sum_{i=0}^{N} {n \choose i}2^i$이므로 $O(3^N)$입니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="k">typedef</span> <span class="n">pair</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="n">p</span><span class="p">;</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">mod</span> <span class="o">=</span> <span class="mi">998244353</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">cnt</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">18</span><span class="p">];</span> <span class="kt">bool</span> <span class="n">g</span><span class="p">[</span><span class="mi">22</span><span class="p">][</span><span class="mi">22</span><span class="p">],</span> <span class="n">chk</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">18</span><span class="p">];</span> <span class="n">ll</span> <span class="n">dp</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">18</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">s</span><span class="o">--</span><span class="p">;</span> <span class="n">e</span><span class="o">--</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">][</span><span class="n">e</span><span class="p">]</span> <span class="o">=</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">][</span><span class="n">s</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">))</span> <span class="p">{</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">k</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">k</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">k</span><span class="p">))</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">g</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]){</span> <span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="k">if</span><span class="p">(</span><span class="n">chk</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">break</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">dp</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="o">^</span><span class="p">(</span><span class="n">i</span><span class="o">&amp;-</span><span class="n">i</span><span class="p">)]</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="p">;</span> <span class="n">j</span><span class="o">=</span><span class="p">(</span><span class="n">i</span><span class="o">&amp;</span><span class="p">(</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">)))</span> <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">chk</span><span class="p">[</span><span class="n">j</span><span class="p">])</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">cnt</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&amp;</span> <span class="mi">1</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">^</span><span class="n">j</span><span class="p">];</span> <span class="k">else</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-=</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="o">^</span><span class="n">j</span><span class="p">];</span> <span class="k">if</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">mod</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">mod</span><span class="p">)</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">%=</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">dp</span><span class="p">[(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">)</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="n">m</span> <span class="o">%</span> <span class="n">mod</span> <span class="o">*</span> <span class="p">(</span><span class="n">mod</span><span class="o">/</span><span class="mi">2</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">mod</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/17643백준18664 Minimums on the Edges2020-10-18T02:57:00+00:002020-10-18T02:57:00+00:00https://justicehui.github.io/ps/2020/10/18/BOJ18664<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/18664</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>DP</li> <li>Bitmask</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N^2 2^N + NS)$</li> </ul> <h3 id="풀이">풀이</h3> <p>$i$번 정점에 붙은 토큰의 개수를 $A_i$, 정점 $U_i, V_i$를 연결하는 간선의 용량을 $B_i = \min(A_{U_i}, A_{V_i})$라고 합시다. 이 문제는 아래 조건을 만족하는 $A_i$를 구하는 문제입니다.</p> <ul> <li>$\sum A_i \leq S$ : $\sum A_i &lt; K$라면 아무 정점에 토큰을 더 붙여주면 됩니다.</li> <li>$\sum B_i$를 최대화</li> </ul> <p>집합 $S_i = {v \vert A_v \geq i}$를 정의합시다. 토큰이 1개 이상 붙어있는 정점들을 덮는 덮개, 2개 이상 붙어있는 정점들을 덮는 덮개, …라고 생각하면 편합니다. $A_i$는 $i$번 정점을 포함하는 집합(덮개)의 개수가 됩니다.<br /> 또한, $B_i$는 ($U_i$를 포함하는 집합)과 (V_i를 포함하는 집합)의 교집합의 크기 = ($U_i, V_i$를 모두 포함하는 교집합의 크기)가 됩니다.</p> <p>$f(S_i)$를 집합 $S_i$에 완전히 포함되는 간선의 개수로 정의하면, $\sum B_i = \sum f(S_i)$입니다. 이제 문제의 조건을 다시 정리합시다.</p> <ol> <li>$\sum \vert S_i \vert \leq S$</li> <li>$S_{i+1} \subset S_i$ : 토큰이 $i+1$개 이상 붙은 정점은 당연히 $i$개 이상 붙어있습니다.</li> <li>$\sum f(S_i)$를 최대화</li> </ol> <p>2번 조건을 제외하고 1번과 3번 조건만 생각하면, 무게가 $\vert S_i \vert$이고 가치가 $f(S_i)$인 knapsack문제가 됩니다. $2^N$개의 부분집합을 모두 보는 것은 $O(2^NS)$로, 너무 느립니다.<br /> 잘 생각해보면, $1 \leq \vert S_i \vert \leq N$이기 때문에, 크기가 $i$이면서 $f(S_i)$가 최대가 되는 $S_i$를 미리 전처리한다면 $O(NS)$에 knapsack문제를 풀 수 있습니다. 크기가 $i$이면서 $f(S_i)$가 최대가 되는 $S_i$는 $O(2^N N^2)$에 구할 수 있습니다.</p> <p>이렇게 구한 최적해는 2번 조건을 항상 만족합니다.<br /> 두 집합 $S_i, S_j$에 대해, $f(S_i) + f(S_j) \leq f(S_i \cup S_j) + f(S_i \cap S_j)$이기 때문에 두 집합이 서로 포함관계에 있는 것이 최적입니다. 그러므로 항상 2번 조건을 만족합니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="kt">int</span> <span class="n">n</span><span class="p">,</span> <span class="n">m</span><span class="p">,</span> <span class="n">k</span><span class="p">,</span> <span class="n">g</span><span class="p">[</span><span class="mi">22</span><span class="p">][</span><span class="mi">22</span><span class="p">],</span> <span class="n">sz</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">18</span><span class="p">];</span> <span class="n">ll</span> <span class="n">fx</span><span class="p">[</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">18</span><span class="p">],</span> <span class="n">c</span><span class="p">[</span><span class="mi">22</span><span class="p">],</span> <span class="n">val</span><span class="p">[</span><span class="mi">22</span><span class="p">],</span> <span class="n">mx</span><span class="p">;</span> <span class="n">ll</span> <span class="n">dp</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="n">prv</span><span class="p">[</span><span class="mi">101010</span><span class="p">];</span> <span class="kt">int</span> <span class="n">ans</span><span class="p">[</span><span class="mi">22</span><span class="p">];</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span> <span class="o">&gt;&gt;</span> <span class="n">m</span> <span class="o">&gt;&gt;</span> <span class="n">k</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">m</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="kt">int</span> <span class="n">s</span><span class="p">,</span> <span class="n">e</span><span class="p">;</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">s</span> <span class="o">&gt;&gt;</span> <span class="n">e</span><span class="p">;</span> <span class="n">s</span><span class="o">--</span><span class="p">;</span> <span class="n">e</span><span class="o">--</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">s</span><span class="p">][</span><span class="n">e</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="n">g</span><span class="p">[</span><span class="n">e</span><span class="p">][</span><span class="n">s</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">bit</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">bit</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">bit</span><span class="o">++</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">bit</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">i</span><span class="p">))</span> <span class="p">{</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">bit</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">))</span> <span class="p">{</span> <span class="n">fx</span><span class="p">[</span><span class="n">bit</span><span class="p">]</span> <span class="o">+=</span> <span class="n">g</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">];</span> <span class="p">}</span> <span class="p">}</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="n">n</span><span class="p">);</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span> <span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="o">^</span><span class="p">(</span><span class="n">i</span><span class="o">&amp;-</span><span class="n">i</span><span class="p">)]</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span> <span class="k">if</span><span class="p">(</span><span class="n">c</span><span class="p">[</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">&lt;</span> <span class="n">fx</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">c</span><span class="p">[</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">fx</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">val</span><span class="p">[</span><span class="n">sz</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="p">}</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;=</span><span class="n">k</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="k">if</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">dp</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">dp</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">dp</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="n">i</span><span class="p">]</span><span class="o">+</span><span class="n">c</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">prv</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="p">}</span> <span class="kt">int</span> <span class="n">idx</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">k</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">dp</span><span class="p">[</span><span class="n">idx</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">dp</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">idx</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">idx</span><span class="p">;</span> <span class="n">i</span><span class="p">;</span> <span class="n">i</span><span class="o">-=</span><span class="n">prv</span><span class="p">[</span><span class="n">i</span><span class="p">]){</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="k">if</span><span class="p">(</span><span class="n">val</span><span class="p">[</span><span class="n">prv</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span> <span class="o">&amp;</span> <span class="p">(</span><span class="mi">1</span> <span class="o">&lt;&lt;</span> <span class="n">j</span><span class="p">))</span> <span class="n">ans</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">++</span><span class="p">,</span> <span class="n">sum</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="k">while</span><span class="p">(</span><span class="n">sum</span> <span class="o">&lt;</span> <span class="n">k</span><span class="p">)</span> <span class="n">sum</span><span class="o">++</span><span class="p">,</span> <span class="n">ans</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="s">" "</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/18664백준11591 VUDU2020-10-17T10:19:00+00:002020-10-17T10:19:00+00:00https://justicehui.github.io/coci/2020/10/17/BOJ11591<h3 id="문제-링크">문제 링크</h3> <ul> <li>http://icpc.me/11591</li> </ul> <h3 id="문제-출처">문제 출처</h3> <ul> <li>2015/2016 COCI #2 5번</li> </ul> <h3 id="사용-알고리즘">사용 알고리즘</h3> <ul> <li>세그먼트 트리</li> </ul> <h3 id="시간복잡도">시간복잡도</h3> <ul> <li>$O(N \log N)$</li> </ul> <h3 id="풀이">풀이</h3> <p>구간 $[l, r]$의 평균이 $P$ 이상이 되는 경우의 수를 구하는 문제입니다.</p> <p>$\frac{S_r - S_{l-1}}{r-l+1} \geq P$는 $S_r - S_{l-1} \geq Pr - P(l-1)$로 바꿀 수 있고, 다시 $S_r - Pr \geq S_{l-1} - P(l-1)$로 바꿀 수 있습니다.<br /> Inversion Counting 하듯이 구하면 됩니다.</p> <h3 id="전체-코드">전체 코드</h3> <div class="language-cpp highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cp">#include &lt;bits/stdc++.h&gt; #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) #define IDX(v, x) lower_bound(all(v), x) - v.begin() </span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> <span class="k">typedef</span> <span class="kt">long</span> <span class="kt">long</span> <span class="n">ll</span><span class="p">;</span> <span class="n">ll</span> <span class="n">tree</span><span class="p">[</span><span class="mi">1010101</span><span class="p">];</span> <span class="kt">void</span> <span class="nf">update</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="k">for</span><span class="p">(</span><span class="n">x</span><span class="o">++</span><span class="p">;</span> <span class="n">x</span><span class="o">&lt;</span><span class="mi">1010101</span><span class="p">;</span> <span class="n">x</span><span class="o">+=</span><span class="n">x</span><span class="o">&amp;-</span><span class="n">x</span><span class="p">)</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">++</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span> <span class="n">ll</span> <span class="n">ret</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="n">x</span><span class="o">++</span><span class="p">;</span> <span class="n">x</span><span class="p">;</span> <span class="n">x</span><span class="o">-=</span><span class="n">x</span><span class="o">&amp;-</span><span class="n">x</span><span class="p">)</span> <span class="n">ret</span> <span class="o">+=</span> <span class="n">tree</span><span class="p">[</span><span class="n">x</span><span class="p">];</span> <span class="k">return</span> <span class="n">ret</span><span class="p">;</span> <span class="p">}</span> <span class="n">ll</span> <span class="nf">query</span><span class="p">(</span><span class="kt">int</span> <span class="n">l</span><span class="p">,</span> <span class="kt">int</span> <span class="n">r</span><span class="p">){</span> <span class="k">return</span> <span class="n">query</span><span class="p">(</span><span class="n">r</span><span class="p">)</span> <span class="o">-</span> <span class="n">query</span><span class="p">(</span><span class="n">l</span><span class="o">-</span><span class="mi">1</span><span class="p">);</span> <span class="p">}</span> <span class="n">ll</span> <span class="n">n</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">1010101</span><span class="p">],</span> <span class="n">k</span><span class="p">,</span> <span class="n">ans</span><span class="p">;</span> <span class="n">vector</span><span class="o">&lt;</span><span class="n">ll</span><span class="o">&gt;</span> <span class="n">comp</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> <span class="n">ios_base</span><span class="o">::</span><span class="n">sync_with_stdio</span><span class="p">(</span><span class="nb">false</span><span class="p">);</span> <span class="n">cin</span><span class="p">.</span><span class="n">tie</span><span class="p">(</span><span class="nb">nullptr</span><span class="p">);</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">k</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-=</span> <span class="n">k</span><span class="o">*</span><span class="n">i</span><span class="p">,</span> <span class="n">comp</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">compress</span><span class="p">(</span><span class="n">comp</span><span class="p">);</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">IDX</span><span class="p">(</span><span class="n">comp</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">ans</span> <span class="o">+=</span> <span class="n">query</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]),</span> <span class="n">update</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span> <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">ans</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div>JusticeHui문제 링크 http://icpc.me/11591