2143.md (15038B)
1 Source: https://codeforces.com/blog/entry/146526 2 3 Thanks everybody for participating in the round! 4 5 [2143A - Вычитание всех длин](/contest/2143/problem/A "Codeforces Round 1051 (Div. 2)") 6 7 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [MateiKing80](/profile/MateiKing80 "Мастер MateiKing80") 8 9 **Solution** 10 11 Tutorial is loading... 12 13 **Code** 14 15 ``` 16 #include <iostream> 17 #include <cassert> 18 #include <vector> 19 #include <algorithm> 20 21 #define debug(x) #x << " = " << x << '\n' 22 23 using ll = long long; 24 #define YES std::cout << "YES" << std::endl; 25 #define NO std::cout << "NO" << std::endl; 26 27 void solve() { 28 int n; 29 std::cin >> n; 30 std::vector<int> p(n); 31 for (int i = 0; i < n; i++) { 32 std::cin >> p[i]; 33 } 34 35 int l = 0, r = n - 1; 36 for (int i = 1; i <= n; i++) { 37 if (p[l] == i) { 38 l++; 39 } else if (p[r] == i) { 40 r--; 41 } else { 42 NO; 43 return; 44 } 45 } 46 YES; 47 } 48 49 int main() { 50 int t; 51 std::cin >> t; 52 for (int tc = 1; tc <= t; tc++) { 53 solve(); 54 } 55 56 return 0; 57 } 58 ``` 59 60 [2143B - Скидки](/contest/2143/problem/B "Codeforces Round 1051 (Div. 2)") 61 62 Author: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio") 63 64 **Solution** 65 66 Tutorial is loading... 67 68 **Code** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 using namespace std; 74 75 int n, k, a[200005], b[200005]; 76 77 void testcase() 78 { 79 cin >> n >> k; 80 for (int i = 1; i <= n; i++) 81 cin >> a[i]; 82 for (int i = 1; i <= k; i++) 83 cin >> b[i]; 84 long long ans = 0; 85 sort(a + 1, a + n + 1); 86 sort(b + 1, b + k + 1); 87 for (int i = 1; i <= n; i++) 88 ans += a[i]; 89 long long id = n + 1; 90 for (int i = 1; i <= k; i++) 91 { 92 id -= b[i]; 93 if (id >= 1) 94 ans -= a[id]; 95 } 96 cout << ans << '\n'; 97 } 98 99 int main() 100 { 101 int tc; 102 cin >> tc; 103 while (tc--) 104 testcase(); 105 return 0; 106 } 107 ``` 108 109 [2143C - Максимальное дерево](/contest/2143/problem/C "Codeforces Round 1051 (Div. 2)") 110 111 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [tvladm](/profile/tvladm "Кандидат в мастера tvladm") 112 113 **Solution** 114 115 Tutorial is loading... 116 117 **Code** 118 119 ``` 120 #include <iostream> 121 #include <cassert> 122 #include <vector> 123 #include <algorithm> 124 #include <queue> 125 126 #define debug(x) #x << " = " << x << '\n' 127 128 using ll = long long; 129 #define YES std::cout << "YES\n" 130 #define NO std::cout << "NO\n" 131 132 struct Edge { 133 int u, v, x, y; 134 }; 135 136 void solve() { 137 int n; 138 std::cin >> n; 139 140 std::vector<int> deg(n, 0); 141 std::vector<std::vector<int>> g(n); 142 std::vector<std::vector<int>> gg(n); 143 144 std::vector<Edge> e(n - 1); 145 146 for (auto &[u, v, x, y] : e) { 147 std::cin >> u >> v >> x >> y; 148 u--, v--; 149 if (x > y) { 150 g[u].push_back(v); 151 gg[v].push_back(u); 152 deg[u]++; 153 } else { 154 g[v].push_back(u); 155 gg[u].push_back(v); 156 deg[v]++; 157 } 158 } 159 160 std::queue<int> q; 161 for (int i = 0; i < n; i++) { 162 if (deg[i] == 0) { 163 q.push(i); 164 } 165 } 166 167 std::vector<int> p(n); 168 169 for (int i = 1; i <= n; i++) { 170 int u = q.front(); 171 p[u] = i; 172 q.pop(); 173 174 for (const auto &v : gg[u]) { 175 deg[v]--; 176 if (deg[v] == 0) { 177 q.push(v); 178 } 179 } 180 } 181 182 for (auto [u, v, x, y] : e) { 183 if (x > y) { 184 assert(p[u] > p[v]); 185 } else if (x < y) { 186 assert(p[u] < p[v]); 187 } 188 } 189 190 for (int x : p) { 191 std::cout << x << ' '; 192 } 193 } 194 195 int main() { 196 #ifdef LOCAL 197 freopen("input.txt", "r", stdin); 198 #endif 199 std::ios_base::sync_with_stdio(false); 200 std::cin.tie(0); 201 std::cout.tie(0); 202 203 int t; 204 std::cin >> t; 205 for (int tc = 1; tc <= t; tc++) { 206 std::cerr << "Case #" << tc << ":\n"; 207 solve(); 208 std::cout << '\n'; 209 } 210 211 return 0; 212 } 213 ``` 214 215 [2143D1 - Раскраска графа инверсий (простая версия)](/contest/2143/problem/D1 "Codeforces Round 1051 (Div. 2)") 216 217 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio") 218 219 **Solution** 220 221 Tutorial is loading... 222 223 **Code** 224 225 ``` 226 #include <bits/stdc++.h> 227 228 using namespace std; 229 230 const int NMAX = 3000; 231 const int modulo = 1e9 + 7; 232 233 void addSelf(int &x, int y) 234 { 235 x += y; 236 if (x >= modulo) 237 x -= modulo; 238 } 239 240 int add(int x, int y) 241 { 242 addSelf(x, y); 243 return x; 244 } 245 246 int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation 247 int dp[2][NMAX + 1][NMAX + 1];///considering elements 1..i, the biggest value is j, and the biggest value preceeded by a bigger one is q 248 249 void testcase() 250 { 251 cin >> n; 252 for (int i = 1; i <= n; i++) 253 cin >> b[i]; 254 for (int i = 1; i <= n; i++) 255 { 256 a[i] = 1; 257 for (int j = 1; j < i; j++) 258 if (b[j] <= b[i]) 259 a[i]++; 260 for (int j = i + 1; j <= n; j++) 261 if (b[j] < b[i]) 262 a[i]++; 263 } 264 for (int i = 0; i < 2; i++) 265 for (int j = 0; j <= n; j++) 266 for (int q = 0; q <= n; q++) 267 dp[i][j][q] = 0; 268 dp[0][0][0] = 1; 269 int cr = 0; 270 for (int i = 1; i <= n; i++) 271 { 272 cr ^= 1; 273 int x = a[i]; 274 for (int j = 0; j <= n; j++) 275 for (int q = 0; q <= n; q++) 276 dp[cr][j][q] = dp[cr ^ 1][j][q]; 277 for (int j = 0; j <= n; j++) 278 { 279 for (int q = 0; q <= j; q++) 280 { 281 if (dp[cr ^ 1][j][q] == 0) 282 continue; 283 if (j > x and x > q) 284 addSelf(dp[cr][j][x], dp[cr ^ 1][j][q]); 285 else if (x > j) 286 addSelf(dp[cr][x][q], dp[cr ^ 1][j][q]); 287 } 288 } 289 } 290 int ans = 0; 291 for (int j = 0; j <= n; j++) 292 { 293 for (int q = 0; q <= n; q++) 294 addSelf(ans, dp[cr][j][q]); 295 } 296 cout << ans << '\n';///empty subsequence inclusive 297 } 298 299 int main() 300 { 301 int tc; 302 cin >> tc; 303 while (tc--) 304 testcase(); 305 return 0; 306 } 307 ``` 308 309 [2143D2 - Раскраска графа инверсий (сложная версия)](/contest/2143/problem/D2 "Codeforces Round 1051 (Div. 2)") 310 311 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio"), Editorial: [anpaio](/profile/anpaio "Международный гроссмейстер anpaio") 312 313 **Solution** 314 315 Tutorial is loading... 316 317 **Code** 318 319 ``` 320 #include <bits/stdc++.h> 321 322 using namespace std; 323 324 const int NMAX = 3000; 325 const int modulo = 1e9 + 7; 326 327 void addSelf(int &x, int y) 328 { 329 x += y; 330 if (x >= modulo) 331 x -= modulo; 332 } 333 334 int add(int x, int y) 335 { 336 addSelf(x, y); 337 return x; 338 } 339 340 int n, a[NMAX + 5], b[NMAX + 5];///b -> initial array, a -> equivalent permutation 341 int bit_lin[NMAX + 5][NMAX + 5], bit_col[NMAX + 5][NMAX + 5];///will use an offset of one because of [0..n] range 342 343 void update_lin(int lin, int pos, int val) 344 { 345 pos++; 346 for (int i = pos; i <= n + 1; i += (i & -i)) 347 addSelf(bit_lin[lin][i], val); 348 } 349 350 void update_col(int col, int pos, int val) 351 { 352 pos++; 353 for (int i = pos; i <= n + 1; i += (i & -i)) 354 addSelf(bit_col[col][i], val); 355 } 356 357 int query_lin(int lin, int pos) 358 { 359 pos++; 360 int rr = 0; 361 for (int i = pos; i > 0; i -= (i & -i)) 362 addSelf(rr, bit_lin[lin][i]); 363 return rr; 364 } 365 366 int query_col(int col, int pos) 367 { 368 pos++; 369 int rr = 0; 370 for (int i = pos; i > 0; i -= (i & -i)) 371 addSelf(rr, bit_col[col][i]); 372 return rr; 373 } 374 375 void testcase() 376 { 377 cin >> n; 378 for (int i = 1; i <= n; i++) 379 cin >> b[i]; 380 for (int i = 1; i <= n; i++) 381 { 382 a[i] = 1; 383 for (int j = 1; j < i; j++) 384 if (b[j] <= b[i]) 385 a[i]++; 386 for (int j = i + 1; j <= n; j++) 387 if (b[j] < b[i]) 388 a[i]++; 389 } 390 for (int i = 0; i <= n + 1; i++) 391 for (int j = 0; j <= n + 1; j++) 392 bit_lin[i][j] = bit_col[i][j] = 0; 393 update_lin(0, 0, 1); 394 update_col(0, 0, 1); 395 for (int i = 1; i <= n; i++) 396 { 397 vector<pair<int, pair<int, int>>> buffs;///where to update at the end 398 int x = a[i]; 399 for (int j = x + 1; j <= n; j++) 400 { 401 int lin, col, buff; 402 lin = j; 403 col = x; 404 buff = query_lin(j, x - 1); 405 buffs.push_back({buff, {lin, col}}); 406 } 407 for (int q = 0; q < x; q++) 408 { 409 int lin, col, buff; 410 lin = x; 411 col = q; 412 buff = query_col(q, x - 1); 413 buffs.push_back({buff, {lin, col}}); 414 } 415 for (auto it : buffs) 416 { 417 update_lin(it.second.first, it.second.second, it.first); 418 update_col(it.second.second, it.second.first, it.first); 419 } 420 } 421 int ans = 0; 422 for (int lin = 0; lin <= n; lin++) 423 addSelf(ans, query_lin(lin, n)); 424 cout << ans << '\n'; 425 } 426 427 int main() 428 { 429 int tc; 430 cin >> tc; 431 while (tc--) 432 testcase(); 433 return 0; 434 } 435 ``` 436 437 [2143E - Сделать хорошей](/contest/2143/problem/E "Codeforces Round 1051 (Div. 2)") 438 439 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM") 440 441 **Solution** 442 443 Tutorial is loading... 444 445 **Code** 446 447 ``` 448 #include <iostream> 449 #include <cassert> 450 #include <vector> 451 #include <algorithm> 452 453 #define debug(x) #x << " = " << x << '\n' 454 455 using ll = long long; 456 #define YES std::cout << "YES\n" 457 #define NO std::cout << "NO\n" 458 459 void solve() { 460 int n; 461 std::cin >> n; 462 463 std::string s; 464 std::cin >> s; 465 466 if (s == "))))))))") { 467 std::cout << "(()(()))"; 468 return; 469 } 470 if (n % 2 == 1) { 471 std::cout << -1; 472 return; 473 } 474 475 int delta = 0; 476 477 assert((int) s.size() == n); 478 479 for (int i = 0; i < (int) s.size(); i++) { 480 int value = (s[i] == '('? +1 : -1); 481 if (i & 1) { 482 value *= -1; 483 } 484 delta += value; 485 } 486 487 if (delta == -n || std::abs(delta) % 4 != n % 4) { 488 std::cout << -1; 489 return; 490 } 491 492 int plus = (n + delta) / 2; 493 int minus = (n - delta) / 2; 494 495 assert(minus % 2 == 0); 496 497 std::cout << "("; 498 for (int i = 0; i < minus / 2; i++) { 499 std::cout << "()"; 500 } 501 std::cout << ")"; 502 for (int i = 0; i < (plus - 2) / 2; i++) { 503 std::cout << "()"; 504 } 505 } 506 507 int main() { 508 std::ios_base::sync_with_stdio(false); 509 std::cin.tie(0); 510 511 int t; 512 std::cin >> t; 513 for (int tc = 1; tc <= t; tc++) { 514 std::cerr << "Case #" << tc << ":\n"; 515 solve(); 516 std::cout << '\n'; 517 } 518 519 return 0; 520 } 521 ``` 522 523 [2143F - Увеличение XOR](/contest/2143/problem/F "Codeforces Round 1051 (Div. 2)") 524 525 Author: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Preparation: [LucaLucaM](/profile/LucaLucaM "Мастер LucaLucaM"), Editorial: [MateiKing80](/profile/MateiKing80 "Мастер MateiKing80") 526 527 **Solution** 528 529 Tutorial is loading... 530 531 **Code** 532 533 ``` 534 #include <iostream> 535 #include <cassert> 536 #include <vector> 537 #include <algorithm> 538 539 #define debug(x) #x << " = " << x << '\n' 540 541 using ll = long long; 542 #define YES std::cout << "YES\n" 543 #define NO std::cout << "NO\n" 544 545 const int B = 21; 546 547 struct XorBasis { 548 std::vector<int> basis; 549 std::vector<int> who; 550 551 int sz; 552 553 void reset() { 554 basis.assign(B, 0); 555 who.clear(); 556 sz = 0; 557 } 558 559 bool add(int x, int index) { 560 for (int i = B - 1; i >= 0; i--) { 561 if (x >> i & 1) { 562 if (!basis[i]) { 563 basis[i] = x; 564 who.push_back(index); 565 sz++; 566 return true; 567 } 568 x ^= basis[i]; 569 } 570 } 571 return false; 572 } 573 574 int kth(int k) { // al k-lea cel mai mic subset xor 575 if (k < 1 || k > (1 << sz)) { 576 return -1; 577 } 578 int x = 0; 579 int cnt = (1 << sz); 580 for (int i = B - 1; i >= 0; i--) { 581 if (basis[i]) { 582 if (k > cnt / 2) { 583 if (!(x >> i & 1)) { 584 x ^= basis[i]; 585 } 586 // il fac sa fie 1 587 k -= cnt / 2; 588 } else { 589 // il fac sa fie 0 590 if (x >> i & 1) { 591 x ^= basis[i]; 592 } 593 } 594 cnt /= 2; 595 } 596 } 597 return x; 598 } 599 600 int count_le(int x) { // cate subset uri au xor < x? 601 if (x < 0) { 602 return 0; 603 } 604 int ret = 0; 605 int cnt = (1 << sz); 606 int mask = 0; 607 for (int i = B - 1; i >= 0; i--) { 608 if (basis[i]) { 609 if (x >> i & 1) { 610 ret += cnt / 2; 611 if (!(mask >> i & 1)) { 612 mask ^= basis[i]; 613 } 614 } else { 615 if (mask >> i & 1) { 616 mask ^= basis[i]; 617 } 618 } 619 cnt /= 2; 620 } else { 621 if ((x ^ mask) >> i & 1) { 622 if (x >> i & 1) { 623 return ret + cnt; 624 } else { 625 return ret; 626 } 627 } 628 } 629 } 630 return ret; 631 } 632 int count_leq(int x) { // <= x 633 return count_le(x + 1); 634 } 635 int jumpK(int value, int k) { 636 int p = count_leq(value); 637 return kth(p + k); 638 } 639 }; 640 641 int main() { 642 #ifdef LOCAL 643 freopen("input.txt", "r", stdin); 644 #endif 645 std::ios_base::sync_with_stdio(false); 646 std::cin.tie(0); 647 std::cout.tie(0); 648 649 int tc; 650 std::cin >> tc; 651 while (tc--) { 652 int n, q; 653 std::cin >> n >> q; 654 std::vector<int> a(n); 655 for (int &x : a) { 656 std::cin >> x; 657 } 658 659 XorBasis B; 660 B.reset(); 661 662 std::vector<int> maxR(n); 663 664 for (int l = n - 1; l >= 0; l--) { 665 if (!B.add(a[l], l)) { 666 std::vector<int> ids = B.who; 667 ids.push_back(l); 668 std::sort(ids.begin(), ids.end()); 669 B.reset(); 670 for (int index : ids) { 671 B.add(a[index], index); 672 } 673 } 674 675 std::sort(B.who.begin(), B.who.end()); 676 677 XorBasis aux; 678 aux.reset(); 679 std::swap(B, aux); 680 681 int r = n - 1; 682 683 int maxExtend = l; 684 int prevIndex = l - 1; 685 int prevValue = -1; 686 687 for (int index : aux.who) { 688 if (index - 1 > maxExtend) { 689 r = std::min(r, maxExtend); 690 break; 691 } 692 int before = (prevValue == -1? -1 : B.jumpK(prevValue, index - 1 - prevIndex)); 693 B.add(a[index], index); 694 int me = B.jumpK(before, 1); 695 if (me == -1) { 696 r = std::min(r, index - 1); 697 break; 698 } 699 maxExtend = index + (1 << B.sz) - B.count_leq(me); 700 prevValue = me; 701 prevIndex = index; 702 } 703 r = std::min(r, maxExtend); 704 705 std::swap(aux, B); 706 maxR[l] = r; 707 } 708 709 while (q--) { 710 int l, r; 711 std::cin >> l >> r; 712 l--, r--; 713 if (r <= maxR[l]) { 714 YES; 715 } else { 716 NO; 717 } 718 } 719 } 720 721 return 0; 722 } 723 ```