codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

685.md (42403B)


      1 Source: https://codeforces.com/blog/entry/45558
      2 
      3 If you notice typos or errors, please send a private message.
      4 
      5 [Div2A Free Ice Cream](//codeforces.com/contest/686/problem/A)
      6 
      7 Author: [cdkrot](/profile/cdkrot "Candidate Master cdkrot")   
      8  Developer: [ch_egor](/profile/ch_egor "Candidate Master ch_egor")
      9 
     10 You just needed to implement the actions described in statement.
     11 
     12 If you solution failed, then you probably forgot to use 64-bit integers or made some small mistake.
     13 
     14 Correct solution:
     15 
     16 **C++ code**
     17 
     18 ```
     19 #include <iostream>
     20 #include <cstdio>
     21 #include <cstdlib>
     22 #include <string>
     23 #include <cstring>
     24 #include <vector>
     25 #include <stack>
     26 #include <queue>
     27 #include <deque>
     28 #include <set>
     29 #include <map>
     30 #include <cassert>
     31 #include <algorithm>
     32 #include <iomanip>
     33 #include <ctime>
     34 #include <cmath>
     35 #include <bitset>
     36 
     37 #pragma comment(linker, "/STACK:256000000")
     38 
     39 using namespace std;
     40 
     41 typedef long long int int64;
     42 typedef long double double80;
     43 
     44 const int INF = (1 << 29) + 5;
     45 const int64 LLINF = (1ll << 59) + 5;
     46 const int MOD = 1000 * 1000 * 1000 + 7;
     47 
     48 const int MAX_N = 1005;
     49 
     50 int n, x, sad;
     51 int64 answer;
     52 
     53 int main()
     54 {
     55 	//freopen("input.txt", "r", stdin);
     56 	//freopen("output.txt", "w", stdout);
     57 
     58 	scanf("%d %d\n", &n, &x);
     59 
     60 	answer = x;
     61 	sad = 0;
     62 
     63 	int cur;
     64 	char type;
     65 	for (int i = 0; i < n; ++i)
     66 	{
     67 		scanf("%c %d\n", &type, &cur);
     68 		if (type == '+')
     69 		{
     70 			answer += cur;
     71 		}
     72 		else if (answer >= cur)
     73 		{
     74 			answer -= cur;
     75 		}
     76 		else
     77 		{
     78 		    ++sad;
     79 		}
     80 	}
     81 
     82 	cout << answer << " " << sad << "\n";
     83 
     84 	fclose(stdin);
     85 	fclose(stdout);
     86 
     87 	return 0;
     88 }
     89 ```
     90 
     91 **Python code**
     92 
     93 ```
     94 import sys
     95 
     96 def main():
     97     n, answer = map(int, sys.stdin.readline().split())
     98     sad = 0
     99 
    100     for i in range(n):
    101         type_of, cur = sys.stdin.readline().split()
    102         cur = int(cur)
    103         if type_of == "+":
    104             answer += cur
    105         elif answer >= cur:
    106             answer -= cur
    107         else:
    108             sad += 1
    109 
    110     sys.stdout.write(str(answer) + " " + str(sad))
    111 
    112 main()
    113 ```
    114 
    115 [Div2B Little Robber Girl's Zoo](//codeforces.com/contest/686/problem/B)
    116 
    117 Author: [ch_egor](/profile/ch_egor "Candidate Master ch_egor")   
    118  Developer: [ch_egor](/profile/ch_egor "Candidate Master ch_egor")
    119 
    120 We need to sort an array with strange operations — namely, to swap elements with even and odd indices in subarray of even length. Note that we can change the 2 neighboring elements, simply doing our exchange action for subarray of length 2 containing these elements. Also, note that *n* ≤ 100, and it is permission to do 20 000 actions, therefore, we can write any quadratic sort, which changes the neighboring elements in each iteration (bubble sort for example).   
    121  Complexity *O*(*n*2)
    122 
    123 **C++ code**
    124 
    125 ```
    126 #include <iostream>
    127 #include <cstdio>
    128 #include <cstdlib>
    129 #include <string>
    130 #include <cstring>
    131 #include <vector>
    132 #include <stack>
    133 #include <queue>
    134 #include <deque>
    135 #include <set>
    136 #include <map>
    137 #include <cassert>
    138 #include <algorithm>
    139 #include <iomanip>
    140 #include <ctime>
    141 #include <cmath>
    142 #include <bitset>
    143 
    144 #pragma comment(linker, "/STACK:256000000")
    145 
    146 using namespace std;
    147 
    148 typedef long long int int64;
    149 typedef long double double80;
    150 
    151 const int INF = (1 << 29) + 5;
    152 const int64 LLINF = (1ll << 59) + 5;
    153 const int MOD = 1000 * 1000 * 1000 + 7;
    154 
    155 const int MAX_N = 105;
    156 
    157 int n;
    158 int arr[MAX_N];
    159 
    160 int main()
    161 {
    162 	//freopen("input.txt", "r", stdin);
    163 	//freopen("output.txt", "w", stdout);
    164 
    165 	scanf("%d", &n);
    166 
    167 	for (int i = 0; i < n; ++i)
    168 	{
    169 		scanf("%d", &arr[i]);
    170 	}
    171 
    172 	for (int i = n - 1; i > 0; --i)
    173 	{
    174 		for (int j = 0; j < i; ++j)
    175 		{
    176 			if (arr[j] > arr[j + 1])
    177 			{
    178 				swap(arr[j], arr[j + 1]);
    179 				printf("%d %d\n", j + 1, j + 2);
    180 			}
    181 		}
    182 	}
    183 
    184 	fclose(stdin);
    185 	fclose(stdout);
    186 
    187 	return 0;
    188 }
    189 ```
    190 
    191 **Python code**
    192 
    193 ```
    194 n = int(input())
    195 arr = list(map(int, input().split()))
    196 
    197 for i in range(n - 1, 0, -1):
    198     for j in range(i):
    199         if arr[j] > arr[j + 1]:
    200             arr[j], arr[j + 1] = arr[j + 1], arr[j]
    201             print(j + 1, j + 2)
    202 ```
    203 
    204 Bonus: Is anyone able to search the shortest solution of this problem? If yes, what complexity?
    205 
    206 [Div2C Robbers' watch](//codeforces.com/contest/686/problem/C)/[Div1A Robbers' watch](//codeforces.com/contest/685/problem/A)
    207 
    208 Author: [cdkrot](/profile/cdkrot "Candidate Master cdkrot")   
    209  Developer: [themikemikovi4](/profile/themikemikovi4 "Expert themikemikovi4")
    210 
    211 In this problem we use the septimal number system. It is a very important limitation. Let's count how many digits are showed on the watch display and call it *cnt*. If *cnt* more than 7, the answer is clearly 0 (because of pigeonhole principle). If *cnt* is not greater than 7, then you can just bruteforces all cases.   
    212  Depending on the implementation it will be *O*(*BASE* *BASE**BASE*), *O*(*BASE**BASE*) or *O*(*BASE* *BASE*!), where *BASE* = 7. Actually the most simple implementation is just to cycle between all posible hour:minute combinations and check them.   
    213  In the worst case, it will work in *O*(*BASE* *BASE**BASE*).
    214 
    215 **C++ code**
    216 
    217 ```
    218 // Copyright (C) 2016 Sayutin Dmitry.
    219 //
    220 // This program is free software; you can redistribute it and/or
    221 // modify it under the terms of the GNU General Public License as
    222 // published by the Free Software Foundation; version 3
    223 
    224 // This program is distributed in the hope that it will be useful,
    225 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    226 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    227 // GNU General Public License for more details.
    228 
    229 // You should have received a copy of the GNU General Public License
    230 // along with this program; If not, see <http://www.gnu.org/licenses/>.
    231 
    232 #include <iostream>
    233 #include <vector>
    234 #include <stdint.h>
    235 #include <algorithm>
    236 #include <set>
    237 #include <map>
    238 #include <array>
    239 #include <queue>
    240 #include <stack>
    241 #include <functional>
    242 #include <utility>
    243 #include <string>
    244 #include <assert.h>
    245 #include <iterator>
    246 
    247 using std::cin;
    248 using std::cout;
    249 using std::cerr;
    250 
    251 using std::vector;
    252 using std::map;
    253 using std::array;
    254 using std::set;
    255 using std::string;
    256 
    257 using std::pair;
    258 using std::make_pair;
    259 
    260 using std::min;
    261 using std::abs;
    262 using std::max;
    263 
    264 using std::sort;
    265 using std::generate;
    266 using std::min_element;
    267 using std::max_element;
    268 
    269 template <typename T>
    270 T input() {
    271     T res;
    272     cin >> res;
    273     return res;
    274 }
    275 
    276 int main() {
    277     std::iostream::sync_with_stdio(false);
    278     cin.tie(nullptr);
    279     cout.tie(nullptr);
    280 
    281     size_t n, m;
    282     cin >> n >> m;
    283 
    284     size_t len1 = 1, len2 = 1;
    285     for (size_t a = 7; a < n; a *= 7)
    286         len1 += 1;
    287     for (size_t b = 7; b < m; b *= 7)
    288         len2 += 1;
    289 
    290     size_t ans = 0;
    291     if (len1 + len2 <= 7)
    292         for (size_t i = 0; i != n; ++i)
    293             for (size_t j = 0; j != m; ++j) {
    294                 vector<size_t> used(7, 0);
    295                 
    296                 for (size_t a = i, k = 0; k != len1; a /= 7, ++k)
    297                     used[a % 7] += 1;
    298                 for (size_t b = j, k = 0; k != len2; b /= 7, ++k)
    299                     used[b % 7] += 1;
    300                 
    301                 if (*std::max_element(used.begin(), used.end()) <= 1)
    302                     ++ans;
    303             }
    304     
    305     cout << ans << "\n";
    306     
    307     return 0;
    308 }
    309 ```
    310 
    311 **Python code**
    312 
    313 ```
    314 BASE = 7
    315 
    316 def itov(x):
    317     digits = []
    318     if x == 0:
    319         digits.append(0)
    320     while x > 0:
    321         digits.append(x % BASE)
    322         x //= BASE
    323     digits.reverse()
    324     return digits
    325 
    326 def gen(pos = 0, minute = False, smaller = False):
    327     max_val = max_minute if minute else max_hour
    328     if pos >= len(max_val):
    329         if minute:
    330             return 1
    331         else:
    332             return gen(0, True)
    333     else:
    334         ans = 0
    335         for digit in range(BASE):
    336             if not used[digit] and (smaller or digit <= max_val[pos]):
    337                 used[digit] = True
    338                 ans += gen(pos + 1, minute, smaller or digit < max_val[pos])
    339                 used[digit] = False
    340         return ans
    341 
    342 n, m = map(int, input().split())
    343 n -= 1
    344 m -= 1
    345 used = [False] * BASE
    346 max_hour = itov(n)
    347 max_minute = itov(m)
    348 print(gen())
    349 ```
    350 
    351 Bonus: Suppose the base is not fixed. Solve a problem with *n* ≤ 109, *m* ≤ 109, *BASE* ≤ 109. Can you do it in ![](https://espresso.codeforces.com/9c58a55f056fa649f2d27bf880c7a4b53ba5ef51.png)?
    352 
    353 [Div2D Kay and Snowflake](//codeforces.com/contest/686/problem/D)/[Div1B Kay and Snowflake](//codeforces.com/contest/685/problem/B)
    354 
    355 Author: [cdkrot](/profile/cdkrot "Candidate Master cdkrot")   
    356  Developers: [ch_egor](/profile/ch_egor "Candidate Master ch_egor"), [cdkrot](/profile/cdkrot "Candidate Master cdkrot")
    357 
    358 There are many possible approaches.
    359 
    360 Solution by [cdkrot](/profile/cdkrot "Candidate Master cdkrot"):
    361 
    362 Look at the all candidates for the centroid of the vertices *v* subtree. The size of centroid subtree must be at least ![](https://espresso.codeforces.com/f17f62ae0f884f7d88d415e3c34059f5f6dbb0d4.png) of the vertex *v* subtree size. (If it isn't, then after cutting the upper part will have too big size)
    363 
    364 Choose the vertex with the smallest subtree size satisfying the constraint above. Let's prove, that this vertex is centroid indeed. If it isn't, then after cutting some part will have subtree size greater than ![](https://espresso.codeforces.com/f17f62ae0f884f7d88d415e3c34059f5f6dbb0d4.png) of subtree size of query vertex. It isn't upper part (because of constraint above), it is one of our sons. Ouch, it's subtree less than of selected vertex, and it's still greater than ![](https://espresso.codeforces.com/f17f62ae0f884f7d88d415e3c34059f5f6dbb0d4.png) of subtree size of query vertex. Contradiction.
    365 
    366 So we find a centroid.   
    367  We write the euler tour of tree and we will use a 2D segment tree in order to search for a vertex quickly.   
    368  Complexity ![](https://espresso.codeforces.com/c229edb967c6df8376a62d78f0b2fcebe037188e.png)
    369 
    370 **C++ code**
    371 
    372 ```
    373 // Copyright (C) 2016 Sayutin Dmitry.
    374 //
    375 // This program is free software; you can redistribute it and/or
    376 // modify it under the terms of the GNU General Public License as
    377 // published by the Free Software Foundation; version 3
    378 
    379 // This program is distributed in the hope that it will be useful,
    380 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    381 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    382 // GNU General Public License for more details.
    383 
    384 // You should have received a copy of the GNU General Public License
    385 // along with this program; If not, see <http://www.gnu.org/licenses/>.
    386 
    387 #include <iostream>
    388 #include <vector>
    389 #include <stdint.h>
    390 #include <algorithm>
    391 #include <set>
    392 #include <map>
    393 #include <array>
    394 #include <queue>
    395 #include <stack>
    396 #include <functional>
    397 #include <utility>
    398 #include <string>
    399 #include <assert.h>
    400 #include <iterator>
    401 
    402 using std::cin;
    403 using std::cout;
    404 using std::cerr;
    405 
    406 using std::vector;
    407 using std::map;
    408 using std::array;
    409 using std::set;
    410 using std::string;
    411 
    412 using std::pair;
    413 using std::make_pair;
    414 
    415 using std::min;
    416 using std::abs;
    417 using std::max;
    418 
    419 using std::sort;
    420 using std::generate;
    421 using std::min_element;
    422 using std::max_element;
    423 
    424 template <typename T>
    425 T input() {
    426     T res;
    427     cin >> res;
    428     return res;
    429 }
    430 
    431 const size_t MAXN = (1 << 19);
    432 vector<size_t> graph[MAXN];
    433 
    434 vector<pair<size_t, size_t>> segm[2 * MAXN - 1];
    435 
    436 #define time TIME_FUCKLIBC
    437 
    438 pair<size_t, size_t> times[MAXN];
    439 size_t time = 0;
    440 
    441 size_t sizes[MAXN];
    442 
    443 void dfs(size_t v) {
    444     size_t sz = 1;
    445     
    446     times[v].first = time++;
    447 
    448     for (size_t u: graph[v]) {
    449         dfs(u);
    450         sz += sizes[u];
    451     }
    452     
    453     times[v].second = time;
    454     segm[MAXN - 1 + times[v].first].emplace_back(sz, v);
    455     
    456     sizes[v] = sz;
    457 }
    458 
    459 void buildseg(size_t node, size_t L, size_t R) {
    460     if (L != R - 1) {
    461         size_t mid = L + (R - L) / 2;
    462         buildseg(2 * node + 1, L, mid);
    463         buildseg(2 * node + 2, mid, R);
    464         
    465         segm[node].resize(segm[2 * node + 1].size() + segm[2 * node + 2].size());
    466         std::merge(segm[2 * node + 1].begin(), segm[2 * node + 1].end(), segm[2 * node + 2].begin(), segm[2 * node + 2].end(), segm[node].begin());
    467     }
    468 }
    469 
    470 pair<size_t, size_t> lowerb(size_t node, size_t L, size_t R, size_t rl, size_t rr, pair<size_t, size_t> minval) {
    471     if (rl <= L and R <= rr) {
    472         auto it = std::lower_bound(segm[node].begin(), segm[node].end(), minval);
    473         if (it == segm[node].end())
    474             return make_pair(SIZE_MAX, SIZE_MAX);
    475         else
    476             return *it;
    477     }
    478     if (R <= rl or rr <= L)
    479         return make_pair(SIZE_MAX, SIZE_MAX);
    480 
    481     size_t mid = L + (R - L) / 2;
    482     return min(lowerb(2 * node + 1, L, mid, rl, rr, minval)
    483               ,lowerb(2 * node + 2, mid, R, rl, rr, minval));
    484 }
    485 
    486 int main() {
    487     std::iostream::sync_with_stdio(false);
    488     cin.tie(nullptr);
    489     cout.tie(nullptr);
    490 
    491     size_t n, q;
    492     cin >> n >> q;
    493     
    494     for (size_t i = 1; i != n; ++i)
    495         graph[input<size_t>() - 1].push_back(i);
    496 
    497     dfs(0);
    498     buildseg(0, 0, MAXN);
    499     
    500     for (size_t i = 0; i != q; ++i) {
    501         size_t v = input<size_t>() - 1;
    502         cout << lowerb(0, 0, MAXN, times[v].first, times[v].second, make_pair((sizes[v] + 1) / 2, 0)).second + 1 << "\n";
    503     }
    504     
    505     return 0;
    506 }
    507 ```
    508 
    509 You can consider all answers by one in dfs using this idea. Use std::set for pair (subtree size, vertex number) and at each vertex merge sets obtained from children. (Also known as "merging sets" idea)   
    510  Thus we get the answers for all vertex and we need only output answers for queries.   
    511  Complexity ![](https://espresso.codeforces.com/2d286e3dcadb48fdc5817eac943e3842cd07b3a2.png)
    512 
    513 **C++ code**
    514 
    515 ```
    516 // Copyright (C) 2016 Sayutin Dmitry.
    517 //
    518 // This program is free software; you can redistribute it and/or
    519 // modify it under the terms of the GNU General Public License as
    520 // published by the Free Software Foundation; version 3
    521 
    522 // This program is distributed in the hope that it will be useful,
    523 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    524 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    525 // GNU General Public License for more details.
    526 
    527 // You should have received a copy of the GNU General Public License
    528 // along with this program; If not, see <http://www.gnu.org/licenses/>.
    529 
    530 #include <iostream>
    531 #include <vector>
    532 #include <stdint.h>
    533 #include <algorithm>
    534 #include <set>
    535 #include <map>
    536 #include <array>
    537 #include <queue>
    538 #include <stack>
    539 #include <functional>
    540 #include <utility>
    541 #include <string>
    542 #include <assert.h>
    543 #include <iterator>
    544 
    545 using std::cin;
    546 using std::cout;
    547 using std::cerr;
    548 
    549 using std::vector;
    550 using std::map;
    551 using std::array;
    552 using std::set;
    553 using std::string;
    554 
    555 using std::pair;
    556 using std::make_pair;
    557 
    558 using std::min;
    559 using std::abs;
    560 using std::max;
    561 
    562 using std::sort;
    563 using std::generate;
    564 using std::min_element;
    565 using std::max_element;
    566 
    567 template <typename T>
    568 T input() {
    569     T res;
    570     cin >> res;
    571     return res;
    572 }
    573 
    574 set<pair<size_t, size_t>> solve(const vector<vector<size_t>>& graph, vector<size_t>& ans, size_t v) {
    575     set<pair<size_t, size_t>> cur;
    576 
    577     for (size_t u: graph[v]) {
    578         auto ch = solve(graph, ans, u);
    579         if (not (ch.size() < cur.size()))
    580             std::swap(ch, cur);
    581         
    582         for (auto elem: ch)
    583             cur.insert(elem);
    584     }
    585 
    586     size_t sz = cur.size() + 1;
    587     cur.emplace(sz, v);
    588 
    589     ans[v] = cur.lower_bound(make_pair((sz + 1) / 2, 0))->second;
    590     
    591     return std::move(cur);
    592 }
    593 
    594 int main() {
    595     std::iostream::sync_with_stdio(false);
    596     cin.tie(nullptr);
    597     cout.tie(nullptr);
    598 
    599     size_t n, q;
    600     cin >> n >> q;
    601     
    602     vector<vector<size_t>> graph(n);
    603     for (size_t i = 1; i != n; ++i)
    604         graph[input<size_t>() - 1].push_back(i);
    605 
    606     vector<size_t> ans(n, SIZE_MAX);
    607 
    608     solve(graph, ans, 0);
    609     
    610     for (size_t i = 0; i != q; ++i)
    611         cout << ans[input<size_t>() - 1] + 1 << "\n";
    612     
    613     return 0;
    614 }
    615 ```
    616 
    617 Solution by [ch_egor](/profile/ch_egor "Candidate Master ch_egor"):   
    618  Solve it for all subtrees. We can solve the problem for some subtree, after solving the problem for all of it's children. Let's choose the heaviest child. Note that the centroid of the child after a certain lifting goes into our centroid. Let's model the lifting.   
    619  Thus we get the answers for all vertex and we need only output answers for queries.   
    620  Complexity *O*(*n* + *q*)
    621 
    622 **C++ code**
    623 
    624 ```
    625 #include <iostream>
    626 #include <cstdio>
    627 #include <cstdlib>
    628 #include <string>
    629 #include <cstring>
    630 #include <vector>
    631 #include <stack>
    632 #include <queue>
    633 #include <deque>
    634 #include <set>
    635 #include <map>
    636 #include <cassert>
    637 #include <algorithm>
    638 #include <iomanip>
    639 #include <ctime>
    640 #include <cmath>
    641 #include <bitset>
    642 
    643 #pragma comment(linker, "/STACK:256000000")
    644 
    645 using namespace std;
    646 
    647 typedef long long int int64;
    648 typedef long double double80;
    649 
    650 const int INF = (1 << 29) + 5;
    651 const int64 LLINF = (1ll << 59) + 5;
    652 const int MOD = 1000 * 1000 * 1000 + 7;
    653 
    654 const int MAX_N = 300 * 1000 + 5;
    655 const int MAX_Q = 300 * 1000 + 5;
    656 
    657 int n, q;
    658 vector<int> graph[MAX_N];
    659 int size_of[MAX_N];
    660 int prev_of[MAX_N];
    661 int big_subtree[MAX_N];
    662 int centroid[MAX_N];
    663 
    664 bool is_centroid_of_subtree(int v, int c)
    665 {
    666 	return ((size_of[v] - size_of[c]) * 2 <= size_of[v] && big_subtree[c] * 2 <= size_of[v]);
    667 }
    668 
    669 void dfs_calc(int v, int p)
    670 {
    671 	big_subtree[v] = 0;
    672 	size_of[v] = 1;
    673 	prev_of[v] = p;
    674 
    675 	for (int i = 0; i < graph[v].size(); ++i)
    676 	{
    677 		dfs_calc(graph[v][i], v);
    678 		size_of[v] += size_of[graph[v][i]];
    679 		big_subtree[v] = max(big_subtree[v], size_of[graph[v][i]]);
    680 	}
    681 }
    682 
    683 void dfs_centroid(int v)
    684 {
    685 	if (size_of[v] == 1)
    686 	{
    687 		centroid[v] = v;
    688 	}
    689 	else
    690 	{
    691 		int ptr = 0;
    692 		for (int i = 0; i < graph[v].size(); ++i)
    693 		{
    694 			dfs_centroid(graph[v][i]);
    695 			if (size_of[graph[v][ptr]] < size_of[graph[v][i]])
    696 			{
    697 				ptr = i;
    698 			}
    699 		}
    700 
    701 		int c = centroid[graph[v][ptr]];
    702 
    703 		while (!is_centroid_of_subtree(v, c))
    704 		{
    705 			c = prev_of[c];
    706 		}
    707 
    708 		centroid[v] = c;
    709 	}
    710 }
    711 
    712 int main()
    713 {
    714 	//freopen("input.txt", "r", stdin);
    715 	//freopen("output.txt", "w", stdout);
    716 
    717 	scanf("%d %d", &n, &q);
    718 
    719 	int v;
    720 	for (int i = 0; i < n - 1; ++i)
    721 	{
    722 		scanf("%d", &v);
    723 		graph[v - 1].push_back(i + 1);
    724 	}
    725 
    726 	dfs_calc(0, 0);
    727 	dfs_centroid(0);
    728 
    729 	for (int i = 0; i < q; ++i)
    730 	{
    731 		scanf("%d", &v);
    732 		printf("%d\n", centroid[v - 1] + 1);
    733 	}
    734 
    735 	fclose(stdin);
    736 	fclose(stdout);
    737 
    738 	return 0;
    739 }
    740 ```
    741 
    742 [Div2E Optimal Point](//codeforces.com/contest/686/problem/E)/[Div1C Optimal Point](//codeforces.com/contest/685/problem/C)
    743 
    744 Author: [cdkrot](/profile/cdkrot "Candidate Master cdkrot")   
    745  Developer: [cdkrot](/profile/cdkrot "Candidate Master cdkrot")
    746 
    747 Let's say few words about ternary search. It works correctly, but too slow.   
    748  It's complexity is ![](https://espresso.codeforces.com/4fa379120ad4b96c2dae0065ec97a720f15d62c1.png), where *n* = 105, and *v* = 1018.   
    749  Don't use it.
    750 
    751 Solution.   
    752  1) Let's make binary search on answer   
    753  2) Consider areas of "good" points (with dist  ≤ *mid*) for each source point.   
    754  3) Intersect those areas and check for solution.
    755 
    756 This area can be decsribed by following inequalities:   
    757  (You can achieve them if you expand modules in inequality "manhattan distance <= const")
    758 
    759 .. ≤ *x* + *y* + *z* ≤ .... ≤  - *x* + *y* + *z* ≤ .... ≤ *x* - *y* + *z* ≤ .... ≤ *x* + *y* - *z* ≤ ..
    760 
    761 .. denote some constants.
    762 
    763 If you intersect set of such system, you will get system of the same form, so let's learn how to solve such system.
    764 
    765 Let's replace some variables:
    766 
    767 *a* =  - *x* + *y* + *z**b* = *x* - *y* + *z**c* = *x* + *y* - *z*
    768 
    769 Then:
    770 
    771 *x* + *y* + *z* = *a* + *b* + *c**x* = (*b* + *c*) / 2*y* = (*a* + *c*) / 2*z* = (*a* + *b*) / 2
    772 
    773 Now the system transforms into:
    774 
    775 .. ≤ *a* ≤ .... ≤ *b* ≤ .... ≤ *c* ≤ .... ≤ *a* + *b* + *c* ≤ ..
    776 
    777 We need to check if the system has solution in integers, also the numbers *a*, *b*, *c* must be of the same parity (have equal remainder after division by 2). (This is required for *x*, *y*, *z* to be integers too)
    778 
    779 Let's get rid of parity constraint. Bruteforce the parity of *a*, *b*, *c* (two cases)
    780 
    781 Make following replacement: *a* = 2*a*' + *r*, *b* = 2*b*' + *r*, *c* = 2*c*' + *r*, where *r* = 0 or *r* = 1. Substitute in equations above, simplify, and gain the same system for *a*', *b*', *c*' without parity constraint.
    782 
    783 And now the system can be solved greedy (At first set *a*, *b*, *c* with minimum, and then raise slowly if necessary).
    784 
    785 Total complexity is ![](https://espresso.codeforces.com/a9a5c884fd28aaad2eaa1e4bcb949163c61a8669.png).
    786 
    787 **C++ code**
    788 
    789 ```
    790 // Copyright (C) 2016 Sayutin Dmitry.
    791 //
    792 // This program is free software; you can redistribute it and/or
    793 // modify it under the terms of the GNU General Public License as
    794 // published by the Free Software Foundation; version 3
    795 
    796 // This program is distributed in the hope that it will be useful,
    797 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    798 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    799 // GNU General Public License for more details.
    800 
    801 // You should have received a copy of the GNU General Public License
    802 // along with this program; If not, see <http://www.gnu.org/licenses/>.
    803 
    804 #include <iostream>
    805 #include <vector>
    806 #include <stdint.h>
    807 #include <algorithm>
    808 #include <set>
    809 #include <map>
    810 #include <array>
    811 #include <queue>
    812 #include <stack>
    813 #include <functional>
    814 #include <utility>
    815 #include <string>
    816 #include <assert.h>
    817 #include <iterator>
    818 
    819 using std::cin;
    820 using std::cout;
    821 using std::cerr;
    822 
    823 using std::vector;
    824 using std::map;
    825 using std::array;
    826 using std::set;
    827 using std::string;
    828 
    829 using std::pair;
    830 using std::make_pair;
    831 
    832 using std::min;
    833 using std::abs;
    834 using std::max;
    835 
    836 using std::sort;
    837 using std::generate;
    838 using std::min_element;
    839 using std::max_element;
    840 
    841 template <typename T>
    842 T input() {
    843     T res;
    844     cin >> res;
    845     return res;
    846 }
    847 
    848 struct coord {
    849     int64_t x;
    850     int64_t y;
    851     int64_t z;
    852 };
    853 
    854 struct equation {
    855     pair<int64_t, int64_t> S;
    856     pair<int64_t, int64_t> a;
    857     pair<int64_t, int64_t> b;
    858     pair<int64_t, int64_t> c;
    859 };
    860 
    861 vector<coord> list;
    862 
    863 equation operator+(const equation& e1, const equation& e2) {
    864     equation res;
    865     res.S = {max(e1.S.first, e2.S.first), min(e1.S.second, e2.S.second)};
    866     res.a = {max(e1.a.first, e2.a.first), min(e1.a.second, e2.a.second)};
    867     res.b = {max(e1.b.first, e2.b.first), min(e1.b.second, e2.b.second)};
    868     res.c = {max(e1.c.first, e2.c.first), min(e1.c.second, e2.c.second)};
    869     return res;
    870 }
    871 
    872 coord get_solution(const equation& eq) {
    873     if ((eq.S.first > eq.S.second)
    874      or (eq.a.first > eq.a.second)
    875      or (eq.b.first > eq.b.second)
    876      or (eq.c.first > eq.c.second))
    877         return coord {INT64_MAX, INT64_MAX, INT64_MAX};
    878         
    879      if ((eq.a.first + eq.b.first + eq.c.first > eq.S.second)
    880      or (eq.a.second + eq.b.second + eq.c.second < eq.S.first))
    881         return coord {INT64_MAX, INT64_MAX, INT64_MAX};
    882 
    883      coord res;
    884      res.x = eq.a.first;
    885      res.y = eq.b.first;
    886      res.z = eq.c.first;
    887      int64_t delta = max(int64_t(0), eq.S.first - res.x - res.y - res.z);
    888 
    889      res.x += min(delta, eq.a.second - eq.a.first);
    890      delta -= min(delta, eq.a.second - eq.a.first);
    891      res.y += min(delta, eq.b.second - eq.b.first);
    892      delta -= min(delta, eq.b.second - eq.b.first);
    893      res.z += min(delta, eq.c.second - eq.c.first);
    894      delta -= min(delta, eq.c.second - eq.c.first);
    895 
    896      assert(delta == 0);
    897      
    898      return res;
    899 }
    900 
    901 int64_t DIV2(int64_t arg) {
    902     return (arg - (arg & 1)) / 2;
    903 }
    904 
    905 coord can(int64_t MAXANS) {
    906     equation eq;
    907     eq.S = eq.a = eq.b = eq.c = {INT64_MIN, INT64_MAX};
    908     
    909     for (const coord& crd: list) {
    910         equation nw;
    911         nw.S = { crd.x + crd.y + crd.z - MAXANS,  crd.x + crd.y + crd.z + MAXANS};
    912         nw.a = {-crd.x + crd.y + crd.z - MAXANS, -crd.x + crd.y + crd.z + MAXANS};
    913         nw.b = { crd.x - crd.y + crd.z - MAXANS,  crd.x - crd.y + crd.z + MAXANS};
    914         nw.c = { crd.x + crd.y - crd.z - MAXANS,  crd.x + crd.y - crd.z + MAXANS};
    915         
    916         eq = eq + nw;
    917     }
    918 
    919     for (int64_t r = 0; r <= 1; ++r) {
    920         equation tr = eq;
    921 
    922         tr.S.first  = DIV2(tr.S.first - 3 * r + 1);
    923         tr.a.first  = DIV2(tr.a.first - r + 1);
    924         tr.b.first  = DIV2(tr.b.first - r + 1);
    925         tr.c.first  = DIV2(tr.c.first - r + 1);
    926 
    927         tr.S.second = DIV2(tr.S.second - 3 * r);
    928         tr.a.second = DIV2(tr.a.second - r);
    929         tr.b.second = DIV2(tr.b.second - r);
    930         tr.c.second = DIV2(tr.c.second - r);
    931 
    932         coord sol = get_solution(tr);
    933         if (sol.x != INT64_MAX) {
    934             coord ans;
    935             ans.x = r + sol.y + sol.z;
    936             ans.y = r + sol.x + sol.z;
    937             ans.z = r + sol.x + sol.y;
    938 
    939             return ans;
    940         }
    941     }
    942     return coord {INT64_MAX, INT64_MAX, INT64_MAX};
    943 }
    944 
    945 int main() {
    946     std::iostream::sync_with_stdio(false);
    947     cin.tie(nullptr);
    948     cout.tie(nullptr);
    949 
    950     list.reserve(100000);
    951     
    952     for (size_t T = input<size_t>(); T != 0; --T) {
    953         list.resize(input<size_t>());
    954         
    955         for (coord& crd: list)
    956             cin >> crd.x >> crd.y >> crd.z;
    957 
    958         int64_t L = -1; // definitely imposible
    959         int64_t R = 3 * int64_t(1000 * 1000 * 1000) * int64_t(1000 * 1000 * 1000) + 10; // definitely possible
    960 
    961         while (R - L > 1) {
    962             int64_t M = L + (R - L) / 2;
    963             if (can(M).x != INT64_MAX)
    964                 R = M;
    965             else
    966                 L = M;
    967         }
    968         coord ans = can(R);
    969         cout << ans.x << " " << ans.y << " " << ans.z << "\n";
    970     }
    971     
    972     return 0;
    973 }
    974 ```
    975 
    976 Bonus. This task can be solved in a lot of modifications, for example euclidian distance instead of manhattan, 2d instead of 3d, floats instead of integers. How to solve this varations?
    977 
    978 [Div1D Kay and Eternity](//codeforces.com/contest/685/problem/D)
    979 
    980 Authors: [platypus179](/profile/platypus179 "Master platypus179"), [Endagorion](/profile/Endagorion "International Grandmaster Endagorion")   
    981  Developer: [platypus179](/profile/platypus179 "Master platypus179")
    982 
    983 Let's solve this problem with scanline. Go through all rows from left to right and maintain the array in which in *j* index we will store the number of points in a square with bottom left coordinate (*i*, *j*), where i is current row of scanline.
    984 
    985 This takes *O*(*MAXCORD*2) time. Note that the set of squares that contain some of the shaded points is not very large, namely — if the point has coordinates (*x*, *y*), then the set of left bottom corners of square is defined as {(*a*, *b*)|*x* - *k* + 1 <  = *a* <  = *x*, *y* - *k* + 1 <  = *b* <  = *y*}. Let's consider each point (*x*, *y*) as the 2 events:   
    986  Add one to the all elements with indexes from *y* - *k* + 1 to *y* on the row *x* - *k* + 1 and take one at the same interval on the row *x* + 1. How to calculate answer? Suppose we update the value of a cell on the row *a*, and before it was updated the value *x* on the row *b*. Let add to the answer for the number of squares containing *x* points value *a* - *b*. We can implement the addition of the segment directly and have *O*(*nk*) for processing all the events that fit in time limit. To get rid of *O*(*MAXCORD*) memory, we need to write all interested in the coordinates before processing events (them no more than nk) and reduce the coordinates in the events. It takes ![](https://espresso.codeforces.com/560c5feb7add2b872c6d4e544e00368316fa6b65.png) time and *O*(*nk*) memory. Now we can execute the previous point in *O*(*nk*) memory.   
    987  Complexity is ![](https://espresso.codeforces.com/205d341ef7f2d8cf1117d8d72dc34637bacaa400.png) time and *O*(*nk*) memory.
    988 
    989 **C++ code**
    990 
    991 ```
    992 #include <iostream>
    993 #include <cstdio>
    994 #include <vector>
    995 #include <string>
    996 #include <algorithm>
    997 
    998 using namespace std;
    999 typedef long long ll;
   1000 
   1001 #define NotANumber -1791791791
   1002 
   1003 struct query {
   1004     int row, l, r; bool a;
   1005     int lbl, ubr;
   1006     query(int _row, int _l, int _r, bool _a) {row = _row; l = _l; r = _r; a = _a;}
   1007     bool operator<(const query& other) const {
   1008         return row < other.row;
   1009     }
   1010 };
   1011 
   1012 int main() {
   1013     int n, k;
   1014     scanf("%d %d", &n, &k);
   1015     vector<pair<int, int> > points(n);
   1016     for (int i = 0; i < n; i++)
   1017         scanf("%d %d", &points[i].first, &points[i].second);
   1018 
   1019     sort(points.begin(), points.end());
   1020     vector<int> xcoords;
   1021     for (int i = 0; i < n; i++) {
   1022         int st;
   1023         if (xcoords.empty())
   1024             st = points[i].first - k + 1;
   1025         else
   1026             st = max(xcoords.back() + 1, points[i].first - k + 1);
   1027         for (int j = st; j <= points[i].first; j++)
   1028             xcoords.push_back(j);
   1029     }
   1030 
   1031     vector<query> qs;
   1032     for (int i = 0; i < n; i++) {
   1033         qs.push_back(query(points[i].second - k + 1, points[i].first - k + 1, points[i].first, 1));
   1034         qs.push_back(query(points[i].second + 1, points[i].first - k + 1, points[i].first, 0));
   1035     }
   1036 
   1037     for (query & q : qs) {
   1038         q.lbl = lower_bound(xcoords.begin(), xcoords.end(), q.l) - xcoords.begin();
   1039         q.ubr = upper_bound(xcoords.begin(), xcoords.end(), q.r) - xcoords.begin();
   1040     }
   1041     
   1042     int xcdssz = xcoords.size();
   1043     xcoords.clear();
   1044     xcoords.shrink_to_fit();
   1045 
   1046     sort(qs.begin(), qs.end());
   1047 
   1048     vector<int> vec(xcdssz, 0);
   1049     vector<int> lastchanged(xcdssz, NotANumber);
   1050     vector<ll> ans(n);
   1051 
   1052     for (query q : qs) {
   1053         int lbl = q.lbl;
   1054         int ubr = q.ubr;
   1055         for (int i = lbl; i < ubr; i++) {
   1056             if (lastchanged[i] != NotANumber && vec[i] != 0) {
   1057                 ans[vec[i] - 1] += q.row - lastchanged[i];
   1058             }
   1059             if (q.a)
   1060                 vec[i]++;
   1061             else
   1062                 vec[i]--;
   1063             lastchanged[i] = q.row;
   1064         }
   1065     }
   1066 
   1067     for (int i = 0; i < n; i++)
   1068         printf("%lld ", ans[i]);
   1069     printf("\n");
   1070     return 0;
   1071 }
   1072 ```
   1073 
   1074 Bonus: ![](https://espresso.codeforces.com/bd8232b4c141f2f16d35cd896a9451684955d3cb.png) time and *O*(*n*) memory.
   1075 
   1076 **C++ code**
   1077 
   1078 ```
   1079 #include <iostream>
   1080 #include <cstdio>
   1081 #include <cstdlib>
   1082 #include <string>
   1083 #include <cstring>
   1084 #include <vector>
   1085 #include <stack>
   1086 #include <queue>
   1087 #include <deque>
   1088 #include <set>
   1089 #include <map>
   1090 #include <cassert>
   1091 #include <algorithm>
   1092 #include <iomanip>
   1093 #include <ctime>
   1094 #include <cmath>
   1095 #include <bitset>
   1096 
   1097 #pragma comment(linker, "/STACK:256000000")
   1098 
   1099 using namespace std;
   1100 
   1101 typedef long long int int64;
   1102 typedef long double double80;
   1103 
   1104 const int INF = (1 << 29) + 5;
   1105 const int64 LLINF = (1ll << 59) + 5;
   1106 const int MOD = 1000 * 1000 * 1000 + 7;
   1107 
   1108 const int MAX_N = 1000 * 100 + 5;
   1109 const int MAX_K = 305;
   1110 
   1111 /** Interface */
   1112 
   1113 inline int readChar();
   1114 template <class T = int> inline T readInt();
   1115 template <class T> inline void writeInt(T x);
   1116 inline void writeChar(int x);
   1117 inline void writeWord(const char *s);
   1118 inline void flush();
   1119 
   1120 /** Read */
   1121 
   1122 static const int buf_size = 20 * 1000 * 1000;
   1123 
   1124 inline int getChar()
   1125 {
   1126 	static char buf[buf_size];
   1127 	static int len = 0, pos = 0;
   1128 	if (pos == len)
   1129 		pos = 0, len = fread(buf, 1, buf_size, stdin);
   1130 	if (pos == len)
   1131 		return -1;
   1132 	return buf[pos++];
   1133 }
   1134 
   1135 inline int readChar()
   1136 {
   1137 	int c = getChar();
   1138 	while (c <= 32)
   1139 		c = getChar();
   1140 	return c;
   1141 }
   1142 
   1143 template <class T>
   1144 inline T readInt()
   1145 {
   1146 	int s = 1, c = readChar();
   1147 	T x = 0;
   1148 	if (c == '-')
   1149 		s = -1, c = getChar();
   1150 	while ('0' <= c && c <= '9')
   1151 		x = x * 10 + c - '0', c = getChar();
   1152 	return s == 1 ? x : -x;
   1153 }
   1154 
   1155 inline int64 readInt64()
   1156 {
   1157 	int s = 1, c = readChar();
   1158 	int64 x = 0;
   1159 	if (c == '-')
   1160 		s = -1, c = getChar();
   1161 	while ('0' <= c && c <= '9')
   1162 		x = x * 10 + c - '0', c = getChar();
   1163 	return s == 1 ? x : -x;
   1164 }
   1165 
   1166 /** Write */
   1167 
   1168 static int write_pos = 0;
   1169 static char write_buf[buf_size];
   1170 
   1171 inline void writeChar(int x)
   1172 {
   1173 	if (write_pos == buf_size)
   1174 		fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
   1175 	write_buf[write_pos++] = x;
   1176 }
   1177 
   1178 inline void flush()
   1179 {
   1180 	if (write_pos)
   1181 		fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
   1182 }
   1183 
   1184 template <class T>
   1185 inline void writeInt(T x)
   1186 {
   1187 	if (x < 0)
   1188 		writeChar('-'), x = -x;
   1189 
   1190 	char s[24];
   1191 	int n = 0;
   1192 	while (x || !n)
   1193 		s[n++] = '0' + x % 10, x /= 10;
   1194 	while (n--)
   1195 		writeChar(s[n]);
   1196 }
   1197 
   1198 inline void writeInt64(int64 x)
   1199 {
   1200 	if (x < 0)
   1201 		writeChar('-'), x = -x;
   1202 
   1203 	char s[24];
   1204 	int n = 0;
   1205 	while (x || !n)
   1206 		s[n++] = '0' + x % 10, x /= 10;
   1207 	while (n--)
   1208 		writeChar(s[n]);
   1209 }
   1210 
   1211 inline void writeWord(const char *s)
   1212 {
   1213 	while (*s)
   1214 		writeChar(*s++);
   1215 }
   1216 
   1217 struct point
   1218 {
   1219 	int x;
   1220 	int y;
   1221 };
   1222 
   1223 struct ask
   1224 {
   1225 	int l;
   1226 	int r;
   1227 	int ptr;
   1228 	int type;
   1229 };
   1230 
   1231 bool cmp(const ask &a, const ask &b)
   1232 {
   1233 	return a.ptr < b.ptr;
   1234 }
   1235 
   1236 int n, k;
   1237 point arr[MAX_N];
   1238 int cord[MAX_N * 2];
   1239 ask asks[MAX_N * 2];
   1240 int cord_len = 0;
   1241 int asks_len = 0;
   1242 bool have_prev_cord[MAX_N * 2];
   1243 bool have_prev_line[MAX_N * 2];
   1244 int last_of_cord[MAX_N * 2];
   1245 int last_of_line[MAX_N * 2];
   1246 int at_cord[MAX_N * 2];
   1247 int at_line[MAX_N * 2];
   1248 int64 answer[MAX_N];
   1249 
   1250 int main()
   1251 {
   1252 	//freopen("input.txt", "r", stdin);
   1253 	//freopen("output.txt", "w", stdout);
   1254 
   1255 	n = readInt();
   1256 	k = readInt();
   1257 
   1258 	for (int i = 0; i < n; ++i)
   1259 	{
   1260 		arr[i].x = readInt();
   1261 		arr[i].y = readInt();
   1262 		cord[cord_len++] = arr[i].x;
   1263 		cord[cord_len++] = arr[i].x - k + 1;
   1264 	}
   1265 
   1266 	sort(cord, cord + 2 * n);
   1267 	cord_len = unique(cord, cord + 2 * n) - cord;
   1268 	
   1269 	for (int i = 0; i < n; ++i)
   1270 	{
   1271 		asks[asks_len].l = lower_bound(cord, cord + cord_len, arr[i].x - k + 1) - cord;
   1272 		asks[asks_len].r = lower_bound(cord, cord + cord_len, arr[i].x) - cord;
   1273 		asks[asks_len].ptr = arr[i].y - k + 1;
   1274 		asks[asks_len].type = 1;
   1275 		++asks_len;
   1276 		asks[asks_len].l = asks[asks_len - 1].l;
   1277 		asks[asks_len].r = asks[asks_len - 1].r;
   1278 		asks[asks_len].ptr = arr[i].y + 1;
   1279 		asks[asks_len].type = -1;
   1280 		++asks_len;
   1281 	}
   1282 
   1283 	sort(asks, asks + asks_len, cmp);
   1284 	memset(answer, 0, sizeof(answer));
   1285 	memset(last_of_cord, 0, sizeof(last_of_cord));
   1286 	memset(last_of_line, 0, sizeof(last_of_line));
   1287 	memset(at_cord, 0, sizeof(at_cord));
   1288 	memset(at_line, 0, sizeof(at_line));
   1289 	memset(have_prev_cord, 0, sizeof(have_prev_cord));
   1290 	memset(have_prev_line, 0, sizeof(have_prev_cord));
   1291 
   1292 	for (int i = 0; i < asks_len; ++i)
   1293 	{
   1294 		for (int j = asks[i].l; j <= asks[i].r; ++j)
   1295 		{
   1296 			if (!have_prev_cord[j])
   1297 			{
   1298 				have_prev_cord[j] = true;
   1299 				last_of_cord[j] = asks[i].ptr;
   1300 				at_cord[j] += asks[i].type;
   1301 			}
   1302 			else
   1303 			{
   1304 				answer[at_cord[j]] += asks[i].ptr - last_of_cord[j];
   1305 
   1306 				last_of_cord[j] = asks[i].ptr;
   1307 				at_cord[j] += asks[i].type;
   1308 			}
   1309 		
   1310 
   1311 			if (j != asks[i].r)
   1312 			{
   1313 				if (!have_prev_line[j])
   1314 				{
   1315 					have_prev_line[j] = true;
   1316 					last_of_line[j] = asks[i].ptr;
   1317 					at_line[j] += asks[i].type;
   1318 				}
   1319 				else
   1320 				{
   1321 					answer[at_line[j]] += 1ll * (cord[j + 1] - cord[j] - 1) * (asks[i].ptr - last_of_line[j]);
   1322 
   1323 					last_of_line[j] = asks[i].ptr;
   1324 					at_line[j] += asks[i].type;
   1325 				}
   1326 			}
   1327 		}
   1328 	}
   1329 
   1330 	for (int i = 1; i <= n; ++i)
   1331 	{
   1332 		writeInt64(answer[i]);
   1333 		writeChar(' ');
   1334 	}
   1335 
   1336 	flush();
   1337 
   1338 	fclose(stdin);
   1339 	fclose(stdout);
   1340 
   1341 	return 0;
   1342 }
   1343 ```
   1344 
   1345 [Div1E Travelling Through the Snow Queen's Kingdom](//codeforces.com/contest/685/problem/E)
   1346 
   1347 Authors: [cdkrot](/profile/cdkrot "Candidate Master cdkrot"), [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP")   
   1348  Developers: [ch_egor](/profile/ch_egor "Candidate Master ch_egor"), [cdkrot](/profile/cdkrot "Candidate Master cdkrot")
   1349 
   1350 Unfortunately, due to my, [cdkrot](/profile/cdkrot "Candidate Master cdkrot"), failure, it was possible to get Ac with *O*(*nm*) solution, I apologise for that.
   1351 
   1352 We propose following solution:   
   1353  Let's solve task with divide & conquer. At first let's lift *l* to the first index, where *s* was mentioned And lower the *r* to the last index, where *t* was mentioned. This will not affect answers, but will make implementation much more easy.
   1354 
   1355 Let's look on all queries. For each query consider it's location relative to centre of edges array. If it's stricly on the left half or on the right half, then solve recursively (You need to implement function like *solve*(*requests*, *l*, *r*)).
   1356 
   1357 How to answer on query, if it contains the centre? Let's precalculate two dp's:
   1358 
   1359 *dp**r*[*i*] =  bitset of vertices you can from to the *v**i* or *u**i* with *l* = *m* and *r* = *i*.
   1360 
   1361 *dp**l*[*i*] =  bitset of vertices you can go to starting from *v**i* or *u**i* with *l* = *i* and *r* = *m* - 1
   1362 
   1363 *v**i* and *u**i* are vertices of i'th edge.
   1364 
   1365 Using this dp the answer is yes if and ony if *dp**l*[*l*][*u*] = *true* and *dp**r*[*r*][*u*] = *true* for some *u*.
   1366 
   1367 All above can be implemented using bitwise operations.   
   1368  So the time is ![](https://espresso.codeforces.com/a39290b7676498247a588484e2132548da6dcb22.png)
   1369 
   1370 **C++ code**
   1371 
   1372 ```
   1373 // Copyright (C) 2016 Sayutin Dmitry.
   1374 //
   1375 // This program is free software; you can redistribute it and/or
   1376 // modify it under the terms of the GNU General Public License as
   1377 // published by the Free Software Foundation; version 3
   1378 
   1379 // This program is distributed in the hope that it will be useful,
   1380 // but WITHOUT ANY WARRANTY; without even the implied warranty of
   1381 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   1382 // GNU General Public License for more details.
   1383 
   1384 // You should have received a copy of the GNU General Public License
   1385 // along with this program; If not, see <http://www.gnu.org/licenses/>.
   1386 
   1387 #include <iostream>
   1388 #include <vector>
   1389 #include <stdint.h>
   1390 #include <algorithm>
   1391 #include <set>
   1392 #include <map>
   1393 #include <array>
   1394 #include <queue>
   1395 #include <stack>
   1396 #include <functional>
   1397 #include <utility>
   1398 #include <string>
   1399 #include <assert.h>
   1400 #include <iterator>
   1401 #include <bitset>
   1402 
   1403 using std::cin;
   1404 using std::cout;
   1405 using std::cerr;
   1406 
   1407 using std::vector;
   1408 using std::map;
   1409 using std::array;
   1410 using std::set;
   1411 using std::string;
   1412 
   1413 using std::pair;
   1414 using std::make_pair;
   1415 
   1416 using std::min;
   1417 using std::abs;
   1418 using std::max;
   1419 
   1420 using std::sort;
   1421 using std::generate;
   1422 using std::min_element;
   1423 using std::max_element;
   1424 
   1425 #define size_t uint32_t
   1426 
   1427 struct Req {
   1428     size_t L;
   1429     size_t R;
   1430     size_t S;
   1431     size_t T;
   1432     size_t ID;
   1433 };
   1434 
   1435 struct Edge {
   1436     size_t v;
   1437     size_t u;
   1438     size_t prev1;
   1439     size_t prev2;
   1440     size_t next1;
   1441     size_t next2;
   1442 };
   1443 
   1444 const size_t MAXQ = 200000;
   1445 const size_t MAXN = 1000;
   1446 const size_t MAXM = 200000;
   1447 
   1448 char answers[MAXQ];
   1449 Edge list[MAXM];
   1450 vector<size_t> last[MAXN];
   1451 
   1452 std::bitset<MAXN> masks_r[MAXM / 2 + 10];
   1453 std::bitset<MAXN> masks_l[MAXM / 2 + 10];
   1454 
   1455 void solve_layer(vector<Req>& requests, size_t l, size_t m, size_t r) {
   1456     bool has = false;
   1457     for (size_t i = 0; i != requests.size(); ++i)
   1458         has or_eq (requests[i].L <= m - 1 and requests[i].R >= m);
   1459     if (not has)
   1460         return;
   1461     
   1462     for (size_t i = 0; i != r - m; ++i) {
   1463         masks_r[i] = std::bitset<MAXN>();
   1464         if (list[m + i].prev1 >= m and list[m + i].prev1 != std::numeric_limits<size_t>::max())
   1465             masks_r[i] |= masks_r[list[m + i].prev1 - m];
   1466         if (list[m + i].prev2 >= m and list[m + i].prev2 != std::numeric_limits<size_t>::max())
   1467             masks_r[i] |= masks_r[list[m + i].prev2 - m];
   1468 
   1469         masks_r[i][list[m + i].v] = true;
   1470         masks_r[i][list[m + i].u] = true;
   1471     }
   1472     
   1473     for (size_t z = 0; z != m - l; ++z) {
   1474         size_t i = (m - l) - 1 - z;
   1475         masks_l[i] = std::bitset<MAXN>();
   1476         
   1477         if (list[l + i].next1 < m)
   1478             masks_l[i] |= masks_l[list[l + i].next1 - l];
   1479         if (list[l + i].next2 < m)
   1480             masks_l[i] |= masks_l[list[l + i].next2 - l];
   1481         masks_l[i][list[l + i].v] = true;
   1482         masks_l[i][list[l + i].u] = true;
   1483     }
   1484 
   1485     for (size_t i = 0; i != requests.size();)
   1486         if (requests[i].L <= m - 1 and requests[i].R >= m) {
   1487             answers[requests[i].ID] = (masks_r[requests[i].R - m] & masks_l[requests[i].L - l]).any();
   1488             std::swap(requests[i], requests.back());
   1489             requests.pop_back();
   1490         } else {
   1491             ++i;
   1492         }
   1493 }
   1494 
   1495 void solve(vector<Req>& requests, size_t l, size_t r) {
   1496     if (l == r - 1) {
   1497         for (auto& req: requests)
   1498             answers[req.ID] = (req.S == list[l].v or req.S == list[l].u)
   1499                           and (req.T == list[l].v or req.T == list[l].u);
   1500         return;
   1501     }
   1502     size_t m = l + (r - l) / 2;
   1503     // [l, m), [m, r).
   1504 
   1505     solve_layer(requests, l, m, r);
   1506 
   1507     vector<Req> right;
   1508     for (size_t i = 0; i != requests.size();)
   1509         if (requests[i].L >= m) {
   1510             right.push_back(requests[i]);
   1511             std::swap(requests[i], requests.back());
   1512             requests.pop_back();
   1513         } else {
   1514             ++i;
   1515         }
   1516 
   1517     requests.shrink_to_fit();
   1518     solve(requests, l, m);
   1519     solve(right, m, r);
   1520 }
   1521 
   1522 int main() {
   1523     size_t n, m, q;
   1524     scanf("%d %d %d", &n, &m, &q);
   1525 
   1526     assert(n <= MAXN);
   1527     assert(q <= MAXQ);
   1528     assert(m <= MAXM);
   1529     
   1530     std::fill(answers, answers + q, 16);
   1531     
   1532     for (size_t i = 0; i != m; ++i) {
   1533         scanf("%d %d", &list[i].v, &list[i].u);
   1534         --list[i].v, --list[i].u;
   1535         list[i].prev1 = list[i].prev2 = list[i].next1 = list[i].next2 = std::numeric_limits<size_t>::max();
   1536         
   1537         if (not last[list[i].v].empty()) {
   1538             list[i].prev1 = last[list[i].v].back();
   1539             
   1540             if (list[last[list[i].v].back()].v == list[i].v)
   1541                 list[last[list[i].v].back()].next1 = i;
   1542             else {
   1543                 list[last[list[i].v].back()].next2 = i;
   1544             }
   1545         }
   1546 
   1547         if (not last[list[i].u].empty()) {
   1548             list[i].prev2 = last[list[i].u].back();
   1549             
   1550             if (list[last[list[i].u].back()].v == list[i].u)
   1551                 list[last[list[i].u].back()].next1 = i;
   1552             else {
   1553                 list[last[list[i].u].back()].next2 = i;
   1554             }
   1555         }
   1556         
   1557         last[list[i].v].push_back(i);
   1558         last[list[i].u].push_back(i);
   1559     }
   1560 
   1561     vector<Req> requests;
   1562     for (size_t i = 0; i != q; ++i) {
   1563         Req req;
   1564         scanf("%d %d %d %d", &req.L, &req.R, &req.S, &req.T);
   1565         --req.L, --req.R, --req.S, --req.T;
   1566         req.ID = i;
   1567         
   1568         auto it1 = std::lower_bound(last[req.S].begin(), last[req.S].end(), req.L);
   1569         auto it2 = std::upper_bound(last[req.T].begin(), last[req.T].end(), req.R);
   1570 
   1571         if (it1 == last[req.S].end() or it2 == last[req.T].begin())
   1572             answers[i] = false;
   1573         else {
   1574             req.L = *it1;
   1575             req.R = *std::prev(it2);
   1576             if (req.L > req.R)
   1577                 answers[i] = false;
   1578             else
   1579                 requests.push_back(req);
   1580         }
   1581     }
   1582     
   1583     solve(requests, 0, m);
   1584 
   1585     for (size_t i = 0; i != q; ++i) {
   1586         printf("%s", (answers[i] ? "Yes\n" : "No\n"));
   1587     }
   1588     
   1589     return 0;
   1590 }
   1591 ```