1195.md (13870B)
1 Source: https://codeforces.com/blog/entry/68471 2 3 [1195A - Drinks Choosing](/contest/1195/problem/A "Codeforces Round 574 (Div. 2)") 4 5 Idea: [budalnik](/profile/budalnik "International Master budalnik") 6 7 Preparation: [budalnik](/profile/budalnik "International Master budalnik") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 // Created by Nikolay Budin 17 18 #ifdef LOCAL 19 # define _GLIBCXX_DEBUG 20 #else 21 # define cerr __get_ce 22 #endif 23 #include <bits/stdc++.h> 24 #define ff first 25 #define ss second 26 #define szof(x) ((int)x.size()) 27 28 using namespace std; 29 typedef long long ll; 30 typedef long double ld; 31 typedef pair<int, int> pii; 32 typedef unsigned long long ull; 33 int const INF = (int)1e9 + 1e3; 34 ll const INFL = (ll)1e18 + 1e6; 35 #ifdef LOCAL 36 mt19937 tw(9450189); 37 #else 38 mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count()); 39 #endif 40 uniform_int_distribution<ll> ll_distr; 41 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; } 42 43 void solve() { 44 int n, k; 45 cin >> n >> k; 46 map<int, int> have; 47 for (int i = 0; i < n; ++i) { 48 int num; 49 cin >> num; 50 have[num]++; 51 } 52 int cnt = 0; 53 int ans = 0; 54 for (pii p : have) { 55 cnt += p.ss % 2; 56 ans += p.ss / 2 * 2; 57 } 58 ans += (cnt + 1) / 2; 59 cout << ans << "\n"; 60 } 61 62 int main() { 63 #ifdef LOCAL 64 auto start_time = clock(); 65 cerr << setprecision(3) << fixed; 66 #endif 67 cout << setprecision(15) << fixed; 68 ios::sync_with_stdio(false); 69 cin.tie(nullptr); 70 71 int test_count = 1; 72 // cin >> test_count; 73 for (int test = 1; test <= test_count; ++test) { 74 solve(); 75 } 76 77 #ifdef LOCAL 78 auto end_time = clock(); 79 cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n"; 80 #endif 81 } 82 ``` 83 84 [1195B - Sport Mafia](/contest/1195/problem/B "Codeforces Round 574 (Div. 2)") 85 86 Idea: ? 87 88 Preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and [cdkrot](/profile/cdkrot "Grandmaster cdkrot") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Solution (binary search)** 95 96 ``` 97 #include <iostream> 98 #include <cmath> 99 100 int main() { 101 long long n, k; 102 std::cin >> n >> k; 103 long long l = -1, r = n + 1; 104 while (r - l > 1) { 105 long long m = (l + r) / 2; 106 if ((n - m) * (n - m + 1) / 2 - m > k) 107 l = m; 108 else 109 r = m; 110 } 111 std::cout << r; 112 return 0; 113 } 114 ``` 115 116 **Solution (formula)** 117 118 ``` 119 #include <iostream> 120 #include <cmath> 121 122 int main() { 123 long long n, k; 124 std::cin >> n >> k; 125 std::cout << static_cast<long long>(round(n + 1.5 - sqrt(2 * (n + k) + 2.75))); 126 return 0; 127 } 128 ``` 129 130 [1195C - Basketball Exercise](/contest/1195/problem/C "Codeforces Round 574 (Div. 2)") 131 132 Idea: [meshanya](/profile/meshanya "Grandmaster meshanya") 133 134 Preparation: [tsarn](/profile/tsarn "Master tsarn") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Solution** 141 142 ``` 143 // Created by Nikolay Budin 144 145 #ifdef LOCAL 146 # define _GLIBCXX_DEBUG 147 #else 148 # define cerr __get_ce 149 #endif 150 #include <bits/stdc++.h> 151 #define ff first 152 #define ss second 153 #define szof(x) ((int)x.size()) 154 155 using namespace std; 156 typedef long long ll; 157 typedef long double ld; 158 typedef pair<int, int> pii; 159 typedef unsigned long long ull; 160 typedef pair<ll, ll> pll; 161 int const INF = (int)1e9 + 1e3; 162 ll const INFL = (ll)1e18 + 1e6; 163 #ifdef LOCAL 164 mt19937 tw(9450189); 165 #else 166 mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count()); 167 #endif 168 uniform_int_distribution<ll> ll_distr; 169 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; } 170 171 void solve() { 172 int n; 173 cin >> n; 174 vector<vector<int>> inp; 175 for (int i = 0; i < 2; ++i) { 176 inp.push_back(vector<int>()); 177 for (int j = 0; j < n; ++j) { 178 int num; 179 cin >> num; 180 inp[i].push_back(num); 181 } 182 } 183 184 pll d = {0, 0}; 185 186 for (int i = 0; i < n; ++i) { 187 pll next = {max(d.ff, d.ss + inp[0][i]), max(d.ss, d.ff + inp[1][i])}; 188 d = next; 189 } 190 191 cout << max(d.ff, d.ss) << "\n"; 192 } 193 194 int main() { 195 #ifdef LOCAL 196 auto start_time = clock(); 197 cerr << setprecision(3) << fixed; 198 #endif 199 cout << setprecision(15) << fixed; 200 ios::sync_with_stdio(false); 201 cin.tie(nullptr); 202 203 int test_count = 1; 204 // cin >> test_count; 205 for (int test = 1; test <= test_count; ++test) { 206 solve(); 207 } 208 209 #ifdef LOCAL 210 auto end_time = clock(); 211 cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n"; 212 #endif 213 } 214 ``` 215 216 [1195D1 - Submarine in the Rybinsk Sea (easy edition)](/contest/1195/problem/D1 "Codeforces Round 574 (Div. 2)") 217 218 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 219 220 Preparation: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution** 227 228 ``` 229 #include <bits/stdc++.h> 230 231 using namespace std; 232 233 const int MOD = 998244353; 234 235 int add(int a, int b) { 236 a += b; 237 if (a >= MOD) a -= MOD; 238 if (a < 0) a += MOD; 239 return a; 240 } 241 242 int mul(int a, int b) { 243 return a * 1ll * b % MOD; 244 } 245 246 int len; 247 vector<int> pw10; 248 249 int f(int a) { 250 int pos = 0; 251 int res = 0; 252 while (a > 0) { 253 int cur = a % 10; 254 a /= 10; 255 res = add(res, mul(cur, pw10[2 * pos])); 256 res = add(res, mul(cur, pw10[2 * pos + 1])); 257 ++pos; 258 } 259 return res; 260 } 261 262 int main() { 263 #ifdef _DEBUG 264 freopen("input.txt", "r", stdin); 265 // freopen("output.txt", "w", stdout); 266 #endif 267 268 pw10 = vector<int>(30); 269 pw10[0] = 1; 270 for (int i = 1; i < 30; ++i) { 271 pw10[i] = mul(pw10[i - 1], 10); 272 } 273 274 int n; 275 cin >> n; 276 int ans = 0; 277 for (int i = 0; i < n; ++i) { 278 int a; 279 cin >> a; 280 len = to_string(a).size(); 281 ans = add(ans, mul(n, f(a))); 282 } 283 284 cout << ans << endl; 285 286 return 0; 287 } 288 ``` 289 290 [1195D2 - Submarine in the Rybinsk Sea (hard edition)](/contest/1195/problem/D2 "Codeforces Round 574 (Div. 2)") 291 292 Idea: [meshanya](/profile/meshanya "Grandmaster meshanya") 293 294 Preparation: [sava-cska](/profile/sava-cska "Grandmaster sava-cska") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Solution** 301 302 ``` 303 // Created by Nikolay Budin 304 305 #ifdef LOCAL 306 # define _GLIBCXX_DEBUG 307 #else 308 # define cerr __get_ce 309 #endif 310 #include <bits/stdc++.h> 311 #define ff first 312 #define ss second 313 #define szof(x) ((int)x.size()) 314 315 using namespace std; 316 typedef long long ll; 317 typedef long double ld; 318 typedef pair<int, int> pii; 319 typedef unsigned long long ull; 320 int const INF = (int)1e9 + 1e3; 321 ll const INFL = (ll)1e18 + 1e6; 322 #ifdef LOCAL 323 mt19937 tw(9450189); 324 #else 325 mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count()); 326 #endif 327 uniform_int_distribution<ll> ll_distr; 328 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; } 329 330 const int MOD = 998244353; 331 332 void add(int& a, int b) { 333 a += b; 334 if (a >= MOD) { 335 a -= MOD; 336 } 337 } 338 339 int sum(int a, int b) { 340 add(a, b); 341 return a; 342 } 343 344 int mult(int a, int b) { 345 return (ll) a * b % MOD; 346 } 347 348 int f(vector<int> const& a, int l) { 349 int res = 0; 350 int p = 1; 351 for (int i = 0; i < max(szof(a), l); ++i) { 352 if (i < l) { 353 p = mult(p, 10); 354 } 355 if (i < szof(a)) { 356 add(res, mult(a[i], p)); 357 p = mult(p, 10); 358 } 359 } 360 return res; 361 } 362 363 int f(int l, vector<int> const& b) { 364 int res = 0; 365 int p = 1; 366 for (int i = 0; i < max(l, szof(b)); ++i) { 367 if (i < szof(b)) { 368 add(res, mult(b[i], p)); 369 p = mult(p, 10); 370 } 371 if (i < l) { 372 p = mult(p, 10); 373 } 374 } 375 return res; 376 } 377 378 void solve() { 379 int n; 380 cin >> n; 381 vector<int> arr; 382 const int MAXL = 11; 383 vector<int> of_len(MAXL); 384 for (int i = 0; i < n; ++i) { 385 int num; 386 cin >> num; 387 arr.push_back(num); 388 int l = 0; 389 int tmp = num; 390 while (tmp) { 391 ++l; 392 tmp /= 10; 393 } 394 of_len[l]++; 395 } 396 int ans = 0; 397 for (int i = 0; i < n; ++i) { 398 vector<int> digits; 399 int tmp = arr[i]; 400 while (tmp) { 401 digits.push_back(tmp % 10); 402 tmp /= 10; 403 } 404 for (int l = 1; l < MAXL; ++l) { 405 int sum = f(digits, l); 406 add(ans, mult(sum, of_len[l])); 407 408 sum = f(l, digits); 409 add(ans, mult(sum, of_len[l])); 410 } 411 } 412 413 cout << ans << "\n"; 414 } 415 416 int main() { 417 #ifdef LOCAL 418 auto start_time = clock(); 419 cerr << setprecision(3) << fixed; 420 #endif 421 cout << setprecision(15) << fixed; 422 ios::sync_with_stdio(false); 423 cin.tie(nullptr); 424 425 int test_count = 1; 426 // cin >> test_count; 427 for (int test = 1; test <= test_count; ++test) { 428 solve(); 429 } 430 431 #ifdef LOCAL 432 auto end_time = clock(); 433 cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n"; 434 #endif 435 } 436 ``` 437 438 [1195E - OpenStreetMap](/contest/1195/problem/E "Codeforces Round 574 (Div. 2)") 439 440 Idea: [budalnik](/profile/budalnik "International Master budalnik") 441 442 Preparation: [ima_ima_go](/profile/ima_ima_go "Specialist ima_ima_go") 443 444 **Tutorial** 445 446 Tutorial is loading... 447 448 **Solution** 449 450 ``` 451 #include <bits/stdc++.h> 452 453 using namespace std; 454 455 long long n, m, a, b, g, x, y, z; 456 vector<deque<long long> > deq; 457 vector<vector<long long> > mi; 458 vector<int> power; 459 const long long MAX_V = 1000000000000000ll; 460 461 void ins(deque<long long>& de, long long val) { 462 while(!de.empty() && de.back() > val) { 463 de.pop_back(); 464 } 465 de.push_back(val); 466 } 467 468 void del(deque<long long>& de, long long val) { 469 if (!de.empty() && de.front() == val) { 470 de.pop_front(); 471 } 472 } 473 474 int main() { 475 ios::sync_with_stdio(0); 476 cin.tie(0); 477 cin >> n >> m; 478 cin >> a >> b; 479 cin >> g >> x >> y >> z; 480 mi.resize(n); 481 deq.resize(m); 482 for (int i = 0; i < n; i++) { 483 mi[i].resize(m); 484 for (int j = 0; j < m; j++) { 485 mi[i][j] = g; 486 g = (g * x + y) % z; 487 } 488 } 489 for (int i = 0; i < m; i++) { 490 for (int j = 0; j < a; j++) { 491 ins(deq[i], mi[j][i]); 492 } 493 } 494 deque<long long> real_deq; 495 for (int i = 0; i < b; i++) { 496 ins(real_deq, deq[i].front()); 497 } 498 long long ans = 0; 499 ans += real_deq.front(); 500 for (int i = b; i < m; i++) { 501 del(real_deq, deq[i - b].front()); 502 ins(real_deq, deq[i].front()); 503 ans += real_deq.front(); 504 } 505 for (int i = a; i < n; i++) { 506 for (int j = 0 ; j < m; j++) { 507 ins(deq[j], mi[i][j]); 508 del(deq[j], mi[i - a][j]); 509 } 510 deque<long long> real_d; 511 for (int j = 0; j < b; j++) { 512 ins(real_d, deq[j].front()); 513 } 514 ans += real_d.front(); 515 for (int j = b; j < m; j++) { 516 del(real_d, deq[j - b].front()); 517 ins(real_d, deq[j].front()); 518 ans += real_d.front(); 519 } 520 } 521 cout << ans << "\n"; 522 } 523 ``` 524 525 [1195F - Geometers Anonymous Club](/contest/1195/problem/F "Codeforces Round 574 (Div. 2)") 526 527 Idea: [craborac](/profile/craborac "International Grandmaster craborac") 528 529 Preparation: [budalnik](/profile/budalnik "International Master budalnik") 530 531 **Tutorial** 532 533 Tutorial is loading... 534 535 **Solution** 536 537 ``` 538 // Created by Nikolay Budin 539 540 #ifdef LOCAL 541 # define _GLIBCXX_DEBUG 542 #else 543 # define cerr __get_ce 544 #endif 545 #include <bits/stdc++.h> 546 #define ff first 547 #define ss second 548 #define szof(x) ((int)x.size()) 549 550 using namespace std; 551 typedef long long ll; 552 typedef long double ld; 553 typedef pair<int, int> pii; 554 typedef unsigned long long ull; 555 int const INF = (int)1e9 + 1e3; 556 ll const INFL = (ll)1e18 + 1e6; 557 #ifdef LOCAL 558 mt19937 tw(9450189); 559 #else 560 mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count()); 561 #endif 562 uniform_int_distribution<ll> ll_distr; 563 ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; } 564 565 struct point { 566 int x, y; 567 point(int _x, int _y) : x(_x), y(_y) {} 568 569 point operator-(point const& other) const { 570 return point(x - other.x, y - other.y); 571 } 572 573 point& operator/=(int num) { 574 x /= num; 575 y /= num; 576 return *this; 577 } 578 579 bool operator<(point const& other) const { 580 return x < other.x || (x == other.x && y < other.y); 581 } 582 }; 583 584 void solve() { 585 int n; 586 cin >> n; 587 vector<vector<point>> polys; 588 vector<point> vecs; 589 vector<int> borders; 590 borders.push_back(0); 591 for (int i = 0; i < n; ++i) { 592 int k; 593 cin >> k; 594 borders.push_back(borders.back() + k); 595 polys.push_back({}); 596 for (int j = 0; j < k; ++j) { 597 int x, y; 598 cin >> x >> y; 599 polys.back().push_back(point(x, y)); 600 } 601 602 for (int j = 0; j < k; ++j) { 603 int next = (j + 1) % k; 604 point v = polys[i][next] - polys[i][j]; 605 int tmp = __gcd(abs(v.x), abs(v.y)); 606 v /= tmp; 607 vecs.push_back(v); 608 } 609 } 610 611 vector<int> arr; 612 map<point, int> inds; 613 for (auto v : vecs) { 614 if (!inds.count(v)) { 615 int tmp = szof(inds); 616 inds[v] = tmp; 617 } 618 arr.push_back(inds[v]); 619 } 620 621 vector<int> next(szof(vecs)); 622 vector<int> last(szof(inds), INF); 623 for (int i = szof(vecs) - 1; i >= 0; --i) { 624 next[i] = last[arr[i]]; 625 last[arr[i]] = i; 626 } 627 628 vector<vector<pii>> here(szof(vecs)); 629 int q; 630 cin >> q; 631 vector<int> ans(q); 632 for (int i = 0; i < q; ++i) { 633 int l, r; 634 cin >> l >> r; 635 --l; 636 l = borders[l]; 637 r = borders[r]; 638 here[l].push_back({r, i}); 639 } 640 641 int bpv = 1; 642 while (bpv < szof(vecs)) { 643 bpv *= 2; 644 } 645 646 vector<int> segtree(bpv * 2); 647 648 function<void(int, int)> segtree_set = [&](int pos, int val) { 649 pos += bpv; 650 segtree[pos] = val; 651 pos /= 2; 652 while (pos) { 653 segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1]; 654 pos /= 2; 655 } 656 }; 657 658 function<int(int, int, int, int, int)> segtree_get = [&](int v, int vl, int vr, int l, int r) { 659 if (vr <= l || r <= vl) { 660 return 0; 661 } 662 if (l <= vl && vr <= r) { 663 return segtree[v]; 664 } 665 int vm = (vl + vr) / 2; 666 return segtree_get(v * 2, vl, vm, l, r) + segtree_get(v * 2 + 1, vm, vr, l, r); 667 }; 668 669 for (int i = 0; i < szof(inds); ++i) { 670 segtree_set(last[i], 1); 671 } 672 673 for (int i = 0; i < szof(vecs); ++i) { 674 for (auto p : here[i]) { 675 ans[p.ss] = segtree_get(1, 0, bpv, i, p.ff); 676 } 677 segtree_set(i, 0); 678 if (next[i] != INF) { 679 segtree_set(next[i], 1); 680 } 681 } 682 683 for (int num : ans) { 684 cout << num << "\n"; 685 } 686 } 687 688 int main() { 689 #ifdef LOCAL 690 auto start_time = clock(); 691 cerr << setprecision(3) << fixed; 692 #endif 693 cout << setprecision(15) << fixed; 694 ios::sync_with_stdio(false); 695 cin.tie(nullptr); 696 697 int test_count = 1; 698 // cin >> test_count; 699 for (int test = 1; test <= test_count; ++test) { 700 solve(); 701 } 702 703 #ifdef LOCAL 704 auto end_time = clock(); 705 cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n"; 706 #endif 707 } 708 ```