2111.md (14009B)
1 Source: https://codeforces.com/blog/entry/143528 2 3 Thank you for participating! I hope you enjoyed the problems. 4 5 [2111A - Energy Crystals](/contest/2111/problem/A "Educational Codeforces Round 179 (Rated for Div. 2)") 6 7 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution (FelixArg)** 14 15 ``` 16 #include<bits/stdc++.h> 17 18 using namespace std; 19 20 #define int long long 21 22 void solve(){ 23 int x; 24 cin >> x; 25 int ans = 0; 26 int a1 = 0, a2 = 0, a3 = 0; 27 while(min({a1, a2, a3}) < x){ 28 if (a1 <= a2 && a1 <= a3){ 29 a1 = min(a2, a3) * 2 + 1; 30 } 31 else if (a2 <= a1 && a2 <= a3){ 32 a2 = min(a1, a3) * 2 + 1; 33 } 34 else{ 35 a3 = min(a1, a2) * 2 + 1; 36 } 37 ans++; 38 } 39 cout << ans << '\n'; 40 } 41 42 signed main() 43 { 44 ios_base::sync_with_stdio(false); 45 cin.tie(0); 46 cout.tie(0); 47 48 int tests = 1; 49 cin >> tests; 50 for (int test = 0; test < tests; test++){ 51 solve(); 52 } 53 return 0; 54 } 55 ``` 56 57 [2111B - Fibonacci Cubes](/contest/2111/problem/B "Educational Codeforces Round 179 (Rated for Div. 2)") 58 59 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 60 61 **Tutorial** 62 63 Tutorial is loading... 64 65 **Solution (FelixArg)** 66 67 ``` 68 #include<bits/stdc++.h> 69 using namespace std; 70 71 #define int long long 72 73 void solve(){ 74 int n, m; 75 cin >> n >> m; 76 vector<vector<int>> a(m); 77 78 for (int i = 0; i < m; i++){ 79 for (int j = 0; j < 3; j++){ 80 int x; 81 cin >> x; 82 a[i].emplace_back(x); 83 } 84 sort(a[i].begin(), a[i].end()); 85 } 86 87 vector<int> fib(n + 5); 88 fib[0] = 1; 89 fib[1] = 2; 90 for (int i = 2; i < n + 1; i++){ 91 fib[i] = fib[i - 1] + fib[i - 2]; 92 } 93 94 for (int i = 0; i < m; i++){ 95 if (a[i][0] >= fib[n - 1] && a[i][1] >= fib[n - 1] && a[i][2] >= fib[n]){ 96 cout << '1'; 97 } 98 else{ 99 cout << '0'; 100 } 101 } 102 cout << '\n'; 103 } 104 105 signed main() 106 { 107 ios_base::sync_with_stdio(false); 108 cin.tie(0); 109 cout.tie(0); 110 111 int tests = 1; 112 cin >> tests; 113 for (int test = 0; test < tests; test++){ 114 solve(); 115 } 116 return 0; 117 } 118 ``` 119 120 [2111C - Equal Values](/contest/2111/problem/C "Educational Codeforces Round 179 (Rated for Div. 2)") 121 122 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Solution (awoo)** 129 130 ``` 131 for _ in range(int(input())): 132 n = int(input()) 133 a = list(map(int, input().split())) 134 i = 0 135 ans = 10**18 136 while i < n: 137 j = i 138 while j < n and a[j] == a[i]: 139 j += 1 140 ans = min(ans, (i + n - j) * a[i]) 141 i = j 142 print(ans) 143 ``` 144 145 [2111D - Creating a Schedule](/contest/2111/problem/D "Educational Codeforces Round 179 (Rated for Div. 2)") 146 147 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution (FelixArg)** 154 155 ``` 156 #include<bits/stdc++.h> 157 158 using namespace std; 159 160 void solve(){ 161 int n, m; 162 cin >> n >> m; 163 vector<int> a(m); 164 for (int i = 0; i < m; i++){ 165 cin >> a[i]; 166 } 167 sort(a.begin(), a.end()); 168 vector<vector<int>> ans(n, vector<int> (6)); 169 170 for (int i = 0; i < n; i += 2){ 171 if (i + 1 == n){ 172 for (int j = 0; j < 6; j++){ 173 if (j % 2 == 0){ 174 ans[i][j] = a[i / 2]; 175 } 176 else{ 177 ans[i][j] = a[m - i / 2 - 1]; 178 } 179 } 180 } 181 else{ 182 for (int j = 0; j < 6; j++){ 183 if (j % 2 == 0){ 184 ans[i][j] = a[i / 2]; 185 ans[i + 1][j] = a[m - i / 2 - 1]; 186 } 187 else{ 188 ans[i][j] = a[m - i / 2 - 1]; 189 ans[i + 1][j] = a[i / 2]; 190 } 191 } 192 } 193 } 194 195 for (int i = 0; i < n; i++){ 196 for (int j = 0; j < 6; j++){ 197 cout << ans[i][j] << ' '; 198 } 199 cout << '\n'; 200 } 201 } 202 203 signed main() 204 { 205 ios_base::sync_with_stdio(false); 206 cin.tie(0); 207 cout.tie(0); 208 209 int tests = 1; 210 cin >> tests; 211 for (int test = 0; test < tests; test++){ 212 solve(); 213 } 214 return 0; 215 } 216 ``` 217 218 [2111E - Changing the String](/contest/2111/problem/E "Educational Codeforces Round 179 (Rated for Div. 2)") 219 220 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution (FelixArg)** 227 228 ``` 229 #include<bits/stdc++.h> 230 using namespace std; 231 232 #define int long long 233 234 void solve(){ 235 int n, q; 236 cin >> n >> q; 237 string s; 238 cin >> s; 239 vector<vector<set<int>>> st(3, vector<set<int>> (3)); 240 for (int i = 0; i < q; i++){ 241 char x, y; 242 cin >> x >> y; 243 st[x - 'a'][y - 'a'].insert(i); 244 } 245 246 for (int i = 0; i < n; i++){ 247 if (s[i] == 'a'){ 248 continue; 249 } 250 251 if (s[i] == 'b'){ 252 if (!st[1][0].empty()){ 253 st[1][0].erase(st[1][0].begin()); 254 s[i] = 'a'; 255 continue; 256 } 257 if (!st[1][2].empty()){ 258 auto ind = *st[1][2].begin(); 259 auto lb = st[2][0].lower_bound(ind); 260 if (lb != st[2][0].end()){ 261 st[1][2].erase(ind); 262 st[2][0].erase(lb); 263 s[i] = 'a'; 264 continue; 265 } 266 } 267 } 268 269 if (s[i] == 'c'){ 270 if (!st[2][0].empty()){ 271 st[2][0].erase(st[2][0].begin()); 272 s[i] = 'a'; 273 continue; 274 } 275 if (!st[2][1].empty()){ 276 auto ind = *st[2][1].begin(); 277 st[2][1].erase(ind); 278 s[i] = 'b'; 279 auto lb = st[1][0].lower_bound(ind); 280 if (lb != st[1][0].end()){ 281 st[1][0].erase(lb); 282 s[i] = 'a'; 283 } 284 } 285 } 286 } 287 288 cout << s << '\n'; 289 } 290 291 signed main() 292 { 293 ios_base::sync_with_stdio(false); 294 cin.tie(0); 295 cout.tie(0); 296 297 int tests = 1; 298 cin >> tests; 299 for (int test = 0; test < tests; test++){ 300 solve(); 301 } 302 return 0; 303 } 304 ``` 305 306 [2111F - Puzzle](/contest/2111/problem/F "Educational Codeforces Round 179 (Rated for Div. 2)") 307 308 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 309 310 **Tutorial** 311 312 Tutorial is loading... 313 314 **Solution (FelixArg)** 315 316 ``` 317 #include<bits/stdc++.h> 318 using namespace std; 319 320 #define int long long 321 322 void solve(){ 323 int p, s; 324 cin >> p >> s; 325 326 if (p > 4 * s){ 327 cout << "-1\n"; 328 return; 329 } 330 if (p > 2 * s){ 331 for (int i = 1; i <= 50000; i++){ 332 if (p * i == (2 + 2 * i) * s){ 333 cout << i << '\n'; 334 for (int j = 0; j < i; j++){ 335 cout << "0 " << j << '\n'; 336 } 337 return; 338 } 339 } 340 cout << "-1\n"; 341 return; 342 } 343 344 int k = 0; 345 while(p > 2){ 346 p -= 2; 347 s -= 1; 348 k++; 349 } 350 351 if (p == 2){ 352 cout << 4 * s * s + 4 * s * k << '\n'; 353 for (int i = 0; i < 2 * s; i++){ 354 for (int j = 0; j < 2 * s; j++){ 355 cout << i << ' ' << j << '\n'; 356 } 357 } 358 for (int i = 0; i < 4 * s * k; i++){ 359 cout << 0 << ' ' << 2 * s + i << '\n'; 360 } 361 } 362 else{ 363 cout << 16 * s * s + 16 * s * k << '\n'; 364 for (int i = 0; i < 4 * s; i++){ 365 for (int j = 0; j < 4 * s; j++){ 366 cout << i << ' ' << j << '\n'; 367 } 368 } 369 for (int i = 0; i < 16 * s * k; i++){ 370 cout << 0 << ' ' << 4 * s + i << '\n'; 371 } 372 } 373 } 374 375 signed main() 376 { 377 ios_base::sync_with_stdio(false); 378 cin.tie(0); 379 cout.tie(0); 380 381 int tests = 1; 382 cin >> tests; 383 for (int test = 0; test < tests; test++){ 384 solve(); 385 } 386 return 0; 387 } 388 ``` 389 390 [2111G - Divisible Subarrays](/contest/2111/problem/G "Educational Codeforces Round 179 (Rated for Div. 2)") 391 392 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 393 394 **Tutorial** 395 396 Tutorial is loading... 397 398 **Solution (FelixArg)** 399 400 ``` 401 #include<bits/stdc++.h> 402 403 using namespace std; 404 405 struct PersistentSegmentTree{ 406 #define _null -1 407 struct Node{ 408 int l, r; 409 int val; 410 Node(): l(-1), r(-1), val(_null) {} 411 }; 412 vector<Node> data; 413 vector<int> roots; 414 PersistentSegmentTree(){} 415 416 inline void copy(int x, int y){ 417 data[x].l = data[y].l; 418 data[x].r = data[y].r; 419 data[x].val = data[y].val; 420 } 421 422 int build(int v, int l, int r, vector<int>& a){ 423 if (data.size() == v){ 424 data.emplace_back(); 425 } 426 if (l == r){ 427 data[v].val = a[l]; 428 return v; 429 } 430 int m = (l + r) / 2; 431 data[v].l = build(data.size(), l, m, a); 432 data[v].r = build(data.size(), m + 1, r, a); 433 data[v].val = max(data[data[v].l].val, data[data[v].r].val); 434 return v; 435 } 436 437 int update(int v, int l, int r, int pos, int val){ 438 int new_v = data.size(); 439 data.emplace_back(); 440 copy(new_v, v); 441 if (l == r){ 442 data[new_v].val = val; 443 return new_v; 444 } 445 int m = (l + r) / 2; 446 if (pos <= m){ 447 data[new_v].l = update(data[v].l, l, m, pos, val); 448 } 449 else{ 450 data[new_v].r = update(data[v].r, m + 1, r, pos, val); 451 } 452 data[new_v].val = max(data[data[new_v].l].val, data[data[new_v].r].val); 453 return new_v; 454 } 455 456 int get(int v, int l, int r, int ql, int qr){ 457 if (ql > qr){ 458 return _null; 459 } 460 if (l == ql && r == qr){ 461 return data[v].val; 462 } 463 int m = (l + r) / 2; 464 return max(get(data[v].l, l, m, ql, min(qr, m)), 465 get(data[v].r, m + 1, r, max(ql, m + 1), qr)); 466 } 467 }; 468 469 void solve(){ 470 int n; 471 cin >> n; 472 473 vector<int> p(n); 474 for(int i = 0; i < n; i++){ 475 cin >> p[i]; 476 p[i]--; 477 } 478 479 vector<pair<int,int>> p2(n); 480 for (int i = 0; i < n; i++){ 481 p2[i] = {p[i], i}; 482 } 483 sort(p2.begin(), p2.end()); 484 485 vector<tuple<int,int,int,int>> seg; 486 set<pair<int,int>> st; 487 488 st.insert({-2, -2}); 489 st.insert({n + 1, n + 1}); 490 491 for (int i = 0; i < n; i++){ 492 auto [val, ind] = p2[i]; 493 auto up = st.lower_bound(pair{ind, -1}); 494 auto down = (--st.lower_bound(pair{ind, -1})); 495 496 int l, r; 497 498 if (down->second == ind - 1 && up->first == ind + 1){ 499 l = down->first, r = up->second; 500 st.erase(up); 501 st.erase(down); 502 } 503 else if (down->second == ind - 1){ 504 l = down->first, r = down->second + 1; 505 st.erase(down); 506 } 507 else if (up->first == ind + 1){ 508 l = up->first - 1, r = up->second; 509 st.erase(up); 510 } 511 else{ 512 l = ind, r = ind; 513 } 514 st.insert({l, r}); 515 516 up = st.lower_bound(pair{l + 1, -1}); 517 down = (--st.lower_bound(pair{l, -1})); 518 519 if (l > 0){ 520 seg.emplace_back(max(0, down->second + 1), l - 1, r, i * 2); 521 } 522 if (r < n - 1){ 523 seg.emplace_back(l, r, min(n - 1, up->first - 1), i * 2 + 1); 524 } 525 } 526 527 sort(seg.begin(), seg.end()); 528 529 vector<tuple<int,int,int>> seg2; 530 for (int i = 0; i < seg.size(); i++){ 531 auto [l1, r1, r2, ind] = seg[i]; 532 seg2.emplace_back(r1 + 1, r2, ind); 533 } 534 sort(seg2.begin(), seg2.end()); 535 536 vector<int> pos(2 * n, -1); 537 for (int i = 0; i < seg2.size(); i++){ 538 auto [l, r, ind] = seg2[i]; 539 pos[ind] = i; 540 } 541 542 set<pair<int,int>> open_left_segs; 543 544 vector<int> cur(2 * n, -1); 545 PersistentSegmentTree tree; 546 tree.roots.emplace_back(tree.build(0, 0, 2 * n - 1, cur)); 547 548 vector<int> T(n, -1); 549 int u = 0; 550 for (int i = 0; i < n; i++){ 551 while(u < seg.size() && get<0>(seg[u]) <= i){ 552 auto [l1, r1, r2, ind] = seg[u]; 553 open_left_segs.insert({r1, pos[ind]}); 554 tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, pos[ind], r2)); 555 u++; 556 } 557 while(!open_left_segs.empty() && open_left_segs.begin()->first < i){ 558 auto [r, ind] = *open_left_segs.begin(); 559 open_left_segs.erase(open_left_segs.begin()); 560 tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, ind, -1)); 561 } 562 T[i] = tree.roots.back(); 563 } 564 565 int q; 566 cin >> q; 567 for (int i = 0; i < q; i++){ 568 if (i % 10 == 0){ 569 cout.flush(); 570 } 571 int l, r; 572 cin >> l >> r; 573 l--; 574 r--; 575 auto lb = lower_bound(seg2.begin(), seg2.end(), tuple{l + 1, -1, -1}); 576 if (lb == seg2.end()){ 577 cout << "NO\n"; 578 continue; 579 } 580 auto lb2 = lower_bound(seg2.begin(), seg2.end(), tuple{r + 1, -1, -1}); 581 582 int val; 583 if (lb2 == seg2.end()){ 584 val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], 2 * n - 1); 585 } 586 else{ 587 val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], pos[get<2>(*lb2)] - 1); 588 } 589 cout << (val >= r ? "YES\n" : "NO\n"); 590 } 591 cout.flush(); 592 } 593 594 signed main() 595 { 596 ios_base::sync_with_stdio(false); 597 cin.tie(0); 598 cout.tie(0); 599 600 int tests = 1; 601 //cin >> tests; 602 for (int test = 0; test < tests; test++){ 603 solve(); 604 } 605 return 0; 606 } 607 ``` 608 609 **Solution (awoo)** 610 611 ``` 612 #include <bits/stdc++.h> 613 614 using namespace std; 615 616 #define forn(i, n) for (int i = 0; i < int(n); ++i) 617 618 const int INF = 1e9; 619 const int LOGN = 18; 620 621 struct solver{ 622 int n; 623 vector<int> p; 624 625 solver(const vector<int> &p) : p(p){ 626 n = p.size(); 627 build(); 628 } 629 630 vector<int> nxtmn, nxtmx; 631 632 vector<vector<int>> up; 633 vector<vector<int>> mx; 634 635 void build(){ 636 nxtmx.resize(n); 637 vector<int> stmn, stmx; 638 for (int i = n - 1; i >= 0; --i){ 639 while (!stmx.empty() && p[stmx.back()] < p[i]) 640 stmx.pop_back(); 641 nxtmx[i] = (stmx.empty() ? n : stmx.back()); 642 stmx.push_back(i); 643 } 644 vector<vector<int>> qr(n + 1); 645 forn(i, n) qr[nxtmx[i]].push_back(i); 646 nxtmn.assign(n, n); 647 for (int i = n - 1; i >= 0; --i){ 648 while (!stmn.empty() && p[stmn.back()] > p[i]) 649 stmn.pop_back(); 650 stmn.push_back(i); 651 for (int j : qr[i]){ 652 int l = 0, r = int(stmn.size()) - 1; 653 while (l <= r){ 654 int m = (l + r) / 2; 655 if (p[stmn[m]] < p[j]){ 656 nxtmn[j] = stmn[m]; 657 l = m + 1; 658 } 659 else{ 660 r = m - 1; 661 } 662 } 663 } 664 } 665 up.assign(n + 1, vector<int>(LOGN)); 666 mx.assign(n + 1, vector<int>(LOGN)); 667 forn(i, n){ 668 up[i][0] = nxtmx[i]; 669 mx[i][0] = nxtmn[i]; 670 } 671 up[n][0] = n; 672 mx[n][0] = 0; 673 for (int j = 1; j < LOGN; ++j) forn(i, n + 1){ 674 up[i][j] = up[up[i][j - 1]][j - 1]; 675 mx[i][j] = max(mx[i][j - 1], mx[up[i][j - 1]][j - 1]); 676 } 677 } 678 679 bool query(int l, int r){ 680 int v = l; 681 for (int i = LOGN - 1; i >= 0; --i){ 682 if (up[v][i] >= r) continue; 683 if (mx[v][i] >= r) return true; 684 v = up[v][i]; 685 } 686 return false; 687 } 688 }; 689 690 int main(){ 691 #ifdef _DEBUG 692 freopen("input.txt", "r", stdin); 693 #endif 694 cin.tie(0); 695 ios::sync_with_stdio(false); 696 int n; 697 cin >> n; 698 vector<vector<int>> p(2, vector<int>(n)); 699 forn(i, n){ 700 cin >> p[0][i]; 701 --p[0][i]; 702 } 703 p[1] = p[0]; 704 reverse(p[1].begin(), p[1].end()); 705 solver p0(p[0]); 706 solver p1(p[1]); 707 int m; 708 cin >> m; 709 forn(i, m){ 710 if (i % 10 == 0){ 711 cout.flush(); 712 } 713 int l, r; 714 cin >> l >> r; 715 --l; -- r; 716 bool ans = p0.query(l, r + 1) || p1.query(n - r - 1, n - l); 717 cout << (ans ? "YES\n" : "NO\n"); 718 } 719 cout.flush(); 720 } 721 ```