686.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 ? 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  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  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  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  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  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 , 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 . 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  time and *O*(*nk*) memory. Now we can execute the previous point in *O*(*nk*) memory. 987 Complexity is  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:  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  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 ```