2152.md (14902B)
1 Source: https://codeforces.com/blog/entry/146988 2 3 Thank you for your participation! 4 5 Problem A, B were authored by [djm03178](/profile/djm03178 "Master djm03178"). 6 7 Problem C was authored by [middle_man](/profile/middle_man "International Grandmaster middle_man"). 8 9 Problem D was authored by [qwerasdfzxcl](/profile/qwerasdfzxcl "Grandmaster qwerasdfzxcl"). 10 11 Problem E, F, G, H1, H2 were authored by [ko_osaga](/profile/ko_osaga "Legendary Grandmaster ko_osaga"). 12 13 [2152A - Increase or Smash](/contest/2152/problem/A) 14 15 **Spoiler** 16 17 Tutorial is loading... 18 19 **Code** 20 21 ``` 22 #include <bits/stdc++.h> 23 using namespace std; 24 25 int main() 26 { 27 ios::sync_with_stdio(false); 28 cin.tie(0); 29 30 int t; 31 cin >> t; 32 while (t--) 33 { 34 int n; 35 cin >> n; 36 set<int> s; 37 for (int i = 0; i < n; i++) 38 { 39 int x; 40 cin >> x; 41 s.insert(x); 42 } 43 cout << s.size() * 2 - 1 << '\n'; 44 } 45 } 46 ``` 47 48 [2152B - Catching the Krug](/contest/2152/problem/B) 49 50 **Spoiler** 51 52 Tutorial is loading... 53 54 **Code** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 60 int main() 61 { 62 ios::sync_with_stdio(false); 63 cin.tie(0); 64 65 int t; 66 cin >> t; 67 while (t--) 68 { 69 int n, ra, ca, rb, cb; 70 cin >> n >> ra >> ca >> rb >> cb; 71 int ans = 0; 72 if (rb > ra) 73 ans = max(ans, rb); 74 else if (rb < ra) 75 ans = max(ans, n - rb); 76 if (cb > ca) 77 ans = max(ans, cb); 78 else if (cb < ca) 79 ans = max(ans, n - cb); 80 cout << ans << '\n'; 81 } 82 } 83 ``` 84 85 [2152C - Triple Removal](/contest/2152/problem/C) 86 87 **Spoiler** 88 89 Tutorial is loading... 90 91 **Code** 92 93 ``` 94 /* 95 * T1 Thanks Round 96 * Problem triple-removal 97 * Main Correct Solution 98 */ 99 100 #include <bits/stdc++.h> 101 using namespace std; 102 103 const int MAX = 250'010; 104 105 int A[MAX]; 106 107 int diff[MAX]; 108 int diffsum[MAX]; 109 110 int sum[2][MAX]; 111 112 void solve() { 113 int N, Q; 114 cin >> N >> Q; 115 int i; 116 for (i = 1; i <= N; i++) cin >> A[i]; 117 for (i = 1; i <= N; i++) { 118 sum[0][i] = sum[0][i - 1]; 119 sum[1][i] = sum[1][i - 1]; 120 sum[A[i]][i]++; 121 122 diff[i] = A[i] != A[i - 1]; 123 diffsum[i] = diffsum[i - 1] + diff[i]; 124 } 125 int l, r; 126 for (i = 1; i <= Q; i++) { 127 cin >> l >> r; 128 129 int z, o; 130 z = sum[0][r] - sum[0][l - 1]; 131 o = sum[1][r] - sum[1][l - 1]; 132 if (z % 3) { 133 cout << -1 << '\n'; 134 continue; 135 } 136 if (o % 3) { 137 cout << -1 << '\n'; 138 continue; 139 } 140 141 int sum = z / 3 + o / 3; 142 if (diffsum[r] - diffsum[l] == (r - l)) sum++; 143 cout << sum << '\n'; 144 } 145 } 146 147 signed main() { 148 ios::sync_with_stdio(false), cin.tie(0); 149 int t, T; 150 cin >> T; 151 for (t = 1; t <= T; t++) solve(); 152 } 153 ``` 154 155 [2152D - Division Versus Addition](/contest/2152/problem/D) 156 157 **Spoiler** 158 159 Tutorial is loading... 160 161 **Code** 162 163 ``` 164 #include <bits/stdc++.h> 165 166 using namespace std; 167 using ll = long long; 168 169 constexpr int MAXN = 250000; 170 171 int a[MAXN + 100]; 172 ll prf[MAXN + 100][4]; 173 174 void solve(){ 175 int n, q; 176 scanf("%d %d", &n, &q); 177 178 for (int i=1;i<=n;i++) scanf("%d", a+i); 179 180 for (int i=1;i<=n;i++){ 181 for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j]; 182 183 int typ = 2; 184 if (popcount((unsigned)a[i]) == 1) typ = 0; 185 else if (popcount((unsigned)a[i]-1) == 1) typ = 1; 186 187 prf[i][typ]++; 188 189 prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i])); 190 } 191 192 while(q--){ 193 int l, r; 194 scanf("%d %d", &l, &r); 195 196 ll cnt[3] = {0}; 197 for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j]; 198 199 ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2; 200 printf("%lld\n", ans); 201 } 202 } 203 204 int main(){ 205 int t; 206 scanf("%d", &t); 207 208 while(t--) solve(); 209 } 210 ``` 211 212 [2152E - Monotone Subsequence](/contest/2152/problem/E) 213 214 **Spoiler** 215 216 Tutorial is loading... 217 218 **Code** 219 220 ``` 221 #include <bits/stdc++.h> 222 using namespace std; 223 using lint = long long; 224 using pi = array<lint, 2>; 225 #define sz(v) ((int)(v).size()) 226 #define all(v) (v).begin(), (v).end() 227 #define cr(v, n) (v).clear(), (v).resize(n); 228 229 void solve() { 230 int n; 231 cin >> n; 232 vector<int> ord(n * n + 1); 233 iota(all(ord), 0); 234 auto query = [&](vector<int> v) { 235 cout << "? " << sz(v); 236 for (auto &x : v) 237 cout << " " << x + 1; 238 cout << endl; 239 int y; 240 cin >> y; 241 v.resize(y); 242 for (auto &x : v) 243 cin >> x, x--; 244 return v; 245 }; 246 vector<int> dp(n * n + 1, n); 247 for (int i = 0; i < n; i++) { 248 auto cur_ord = query(ord); 249 if (sz(cur_ord) > n) { 250 cout << "!"; 251 for (int i = 0; i < n+1; i++) 252 cout << " " << cur_ord[i] + 1; 253 cout << endl; 254 return; 255 } 256 vector<int> new_ord; 257 for (auto &x : ord) { 258 if (!binary_search(all(cur_ord), x)) { 259 new_ord.push_back(x); 260 } else dp[x] = i; 261 } 262 ord = new_ord; 263 } 264 int cur = n; 265 vector<int> ans; 266 for (int i = n * n; i >= 0; i--) { 267 if (dp[i] == cur) { 268 ans.push_back(i); 269 cur--; 270 } 271 } 272 if(sz(ans) != n + 1){ 273 cerr << cur << endl; 274 for(auto &x : dp) cerr << x << " "; 275 cerr << endl; 276 } 277 reverse(all(ans)); 278 assert(sz(ans) == n+1); 279 cout << "!"; 280 for (auto &x : ans) 281 cout << " " << x + 1; 282 cout << endl; 283 } 284 285 int main() { 286 int tc; 287 cin >> tc; 288 while (tc--) 289 solve(); 290 } 291 ``` 292 293 [2152F - Triple Attack](/contest/2152/problem/F) 294 295 **Spoiler** 296 297 Tutorial is loading... 298 299 **Code** 300 301 ``` 302 #include <bits/stdc++.h> 303 using namespace std; 304 using lint = long long; 305 using pi = array<lint, 2>; 306 #define sz(v) ((int)(v).size()) 307 #define all(v) (v).begin(), (v).end() 308 #define cr(v, n) (v).clear(), (v).resize(n); 309 const int MAXN = 500005; 310 311 int nxt1[20][MAXN], dep1[MAXN]; 312 pi nxt2[20][MAXN]; 313 314 int main() { 315 ios::sync_with_stdio(false); 316 cin.tie(0); 317 cout.tie(0); 318 319 int T; 320 cin >> T; 321 322 while (T--){ 323 int n, t; 324 cin >> n >> t; 325 t++; 326 vector<int> a(n); 327 for (int i = 0; i < n; i++) 328 cin >> a[i]; 329 330 // EDIT: added init statements for globals 331 for (int i = 0; i < n+5; i++){ 332 for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0}; 333 dep1[i]=0; 334 } 335 336 int j = 0; 337 for (int i = 0; i < n; i++) { 338 while (j < n && a[j] < a[i] + t) 339 j++; 340 nxt1[0][i] = j; 341 } 342 nxt1[0][n] = n; 343 for (int i = n - 1; i >= 0; i--) 344 dep1[i] = dep1[nxt1[0][i]] + 1; 345 for (int i = 1; i < 20; i++) { 346 for (int j = 0; j <= n; j++) 347 nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]]; 348 } 349 auto lca = [&](int u, int v) { 350 if (dep1[u] > dep1[v]) 351 swap(u, v); 352 int dx = dep1[v] - dep1[u]; 353 for (int i = 0; dx; i++) { 354 if (dx & 1) { 355 v = nxt1[i][v]; 356 } 357 dx >>= 1; 358 } 359 if (u == v) 360 return u; 361 for (int i = 19; i >= 0; i--) { 362 if (nxt1[i][u] != nxt1[i][v]) { 363 u = nxt1[i][u]; 364 v = nxt1[i][v]; 365 } 366 } 367 return nxt1[0][u]; 368 }; 369 for (int i = 0; i < n; i++) { 370 int z = lca(i, i + 1); 371 nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]}; 372 } 373 nxt2[0][n] = pi{n, 0}; 374 for (int i = 1; i < 20; i++) { 375 for (int j = 0; j <= n; j++) { 376 auto [n1, d1] = nxt2[i - 1][j]; 377 auto [n2, d2] = nxt2[i - 1][n1]; 378 nxt2[i][j] = pi{n2, d1 + d2}; 379 } 380 } 381 auto gp = [&](int l, int r) { 382 int ans = 0; 383 for (int i = 19; i >= 0; i--) { 384 if (nxt1[i][l] < r) { 385 l = nxt1[i][l]; 386 ans += (1 << i); 387 } 388 } 389 return ans + 1; 390 }; 391 int q; 392 cin >> q; 393 while (q--) { 394 int l, r; 395 cin >> l >> r; 396 l--; 397 if (r - l <= 2) { 398 cout << r - l << "\n"; 399 continue; 400 } 401 int ans = 0; 402 for (int i = 19; i >= 0; i--) { 403 if (nxt2[i][l][0] < r) { 404 ans += nxt2[i][l][1]; 405 l = nxt2[i][l][0]; 406 } 407 } 408 if (l + 1 <= r) 409 ans += gp(l, r); 410 if (l + 2 <= r) 411 ans += gp(l + 1, r); 412 cout << ans << "\n"; 413 } 414 } 415 } 416 ``` 417 418 [2152G - Query Jungle](/contest/2152/problem/G) 419 420 **Spoiler** 421 422 Tutorial is loading... 423 424 **Code** 425 426 ``` 427 #include <bits/stdc++.h> 428 using namespace std; 429 using lint = long long; 430 using pi = array<lint, 2>; 431 #define sz(a) ((int)(a).size()) 432 #define all(a) (a).begin(), (a).end() 433 const int MAXN = 250005; 434 const int MAXT = 1050000; 435 436 struct mtrx { 437 int nxt[2]; 438 mtrx() { nxt[0] = nxt[1] = 0; } 439 mtrx(int x) { 440 nxt[x] = 1; 441 nxt[1 ^ x] = 0; 442 } 443 mtrx operator+(const mtrx &m) const { 444 mtrx ret; 445 ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2]; 446 ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2]; 447 return ret; 448 } 449 }; 450 451 struct node { 452 mtrx M[2]; 453 int lazy; 454 node operator+(const node &nd) const { 455 node ret; 456 ret.M[0] = M[0] + nd.M[0]; 457 ret.M[1] = M[1] + nd.M[1]; 458 ret.lazy = 0; 459 return ret; 460 } 461 } tree[MAXT]; 462 463 void init(int s, int e, int p, vector<pi> &seq) { 464 if (s == e) { 465 tree[p].M[seq[s][0]] = mtrx(seq[s][1]); 466 tree[p].M[1 ^ seq[s][0]] = mtrx(); 467 return; 468 } 469 int m = (s + e) / 2; 470 init(s, m, 2 * p, seq); 471 init(m + 1, e, 2 * p + 1, seq); 472 tree[p] = tree[2 * p] + tree[2 * p + 1]; 473 } 474 475 void lazydown(int p) { 476 if (tree[p].lazy) { 477 for (int i = 2 * p; i < 2 * p + 2; i++) { 478 tree[i].lazy ^= 1; 479 swap(tree[i].M[0], tree[i].M[1]); 480 } 481 tree[p].lazy = 0; 482 } 483 } 484 485 void update(int s, int e, int ps, int pe, int p) { 486 if (e < ps || pe < s) 487 return; 488 if (s <= ps && pe <= e) { 489 tree[p].lazy ^= 1; 490 swap(tree[p].M[0], tree[p].M[1]); 491 return; 492 } 493 int pm = (ps + pe) / 2; 494 lazydown(p); 495 update(s, e, ps, pm, 2 * p); 496 update(s, e, pm + 1, pe, 2 * p + 1); 497 tree[p] = tree[2 * p] + tree[2 * p + 1]; 498 } 499 500 int query() { return tree[1].M[1].nxt[0] / 2; } 501 502 vector<int> gph[MAXN]; 503 int a[MAXN], din[MAXN], dout[MAXN]; 504 vector<pi> seq; 505 506 void dfs(int x, int p = -1) { 507 din[x] = sz(seq); 508 seq.push_back({a[x], 0}); 509 for (auto &y : gph[x]) { 510 if (y != p) 511 dfs(y, x); 512 } 513 seq.push_back({a[x], 1}); 514 dout[x] = sz(seq); 515 } 516 517 int main() { 518 ios::sync_with_stdio(false); 519 cin.tie(0); 520 cout.tie(0); 521 int T; cin >> T; 522 while (T--) { 523 int n; 524 cin >> n; 525 for (int i = 0; i < n; i++) 526 cin >> a[i]; 527 528 for (int i = 0; i < n; i++) gph[i].clear(); 529 seq.clear(); 530 531 for (int i = 0; i < n - 1; i++) { 532 int u, v; 533 cin >> u >> v; 534 u--; 535 v--; 536 gph[u].push_back(v); 537 gph[v].push_back(u); 538 } 539 dfs(0); 540 init(0, sz(seq) - 1, 1, seq); 541 cout << query() << "\n"; 542 int q; 543 cin >> q; 544 while (q--) { 545 int v; 546 cin >> v; 547 v--; 548 update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1); 549 cout << query() << "\n"; 550 } 551 } 552 } 553 ``` 554 555 [2152H1 - Victorious Coloring (Easy Version)](/contest/2152/problem/H1) 556 557 **Spoiler** 558 559 Tutorial is loading... 560 561 **Code** 562 563 ``` 564 #include <bits/stdc++.h> 565 using namespace std; 566 using lint = long long; 567 using pi = array<lint, 2>; 568 #define sz(v) ((int)(v).size()) 569 #define all(v) (v).begin(), (v).end() 570 #define cr(v, n) (v).clear(), (v).resize(n); 571 572 vector<int> pa; 573 574 int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); } 575 576 int main() { 577 ios::sync_with_stdio(false); 578 cin.tie(0); 579 cout.tie(0); 580 int T; cin>>T; 581 while (T--){ 582 int n; 583 cin >> n; 584 vector<array<lint, 3>> edges; 585 for (int i = 0; i < n - 1; i++) { 586 lint u, v, w; 587 cin >> u >> v >> w; 588 u--; 589 v--; 590 edges.push_back({w, u, v}); 591 } 592 sort(all(edges)); 593 reverse(all(edges)); 594 cr(pa, 2 * n - 1); 595 vector<lint> cost(2 * n - 1); 596 vector<pi> ch(2 * n - 1); 597 iota(all(pa), 0); 598 for (int i = 0; i < n - 1; i++) { 599 int u = find(edges[i][1]); 600 int v = find(edges[i][2]); 601 pa[u] = i + n; 602 pa[v] = i + n; 603 ch[i + n] = {u, v}; 604 cost[edges[i][1]] += edges[i][0]; 605 cost[edges[i][2]] += edges[i][0]; 606 cost[i + n] -= edges[i][0] * 2; 607 } 608 for (int i = n; i < 2 * n - 1; i++) { 609 cost[i] += cost[ch[i][0]] + cost[ch[i][1]]; 610 } 611 int q; 612 cin >> q; 613 while (q--) { 614 lint x; 615 cin >> x; 616 vector<lint> dp(2 * n - 1); 617 lint dap = 0; 618 for (int i = 0; i < 2 * n - 1; i++) { 619 if (i >= n) { 620 dp[i] += dp[ch[i][0]] + dp[ch[i][1]]; 621 } 622 if (dp[i] + cost[i] < x) { 623 dap += x - cost[i] - dp[i]; 624 dp[i] = x - cost[i]; 625 } 626 } 627 cout << dap << "\n"; 628 } 629 } 630 } 631 ``` 632 633 [2152H2 - Victorious Coloring (Hard Version)](/contest/2152/problem/H2) 634 635 **Spoiler** 636 637 Tutorial is loading... 638 639 **Code** 640 641 ``` 642 #include <bits/stdc++.h> 643 using namespace std; 644 using lint = long long; 645 using pi = array<lint, 2>; 646 #define sz(v) ((int)(v).size()) 647 #define all(v) (v).begin(), (v).end() 648 #define cr(v, n) (v).clear(), (v).resize(n); 649 650 vector<int> pa; 651 652 int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); } 653 654 int main() { 655 ios::sync_with_stdio(false); 656 cin.tie(0); 657 cout.tie(0); 658 int T; cin>>T; 659 while (T--){ 660 int n; 661 cin >> n; 662 vector<array<lint, 3>> edges; 663 for (int i = 0; i < n - 1; i++) { 664 lint u, v, w; 665 cin >> u >> v >> w; 666 u--; 667 v--; 668 edges.push_back({w, u, v}); 669 } 670 sort(all(edges)); 671 reverse(all(edges)); 672 cr(pa, 2 * n - 1); 673 vector<lint> cost(2 * n - 1); 674 vector<pi> ch(2 * n - 1); 675 iota(all(pa), 0); 676 for (int i = 0; i < n - 1; i++) { 677 int u = find(edges[i][1]); 678 int v = find(edges[i][2]); 679 pa[u] = i + n; 680 pa[v] = i + n; 681 ch[i + n] = {u, v}; 682 cost[edges[i][1]] += edges[i][0]; 683 cost[edges[i][2]] += edges[i][0]; 684 cost[i + n] -= edges[i][0] * 2; 685 } 686 for (int i = n; i < 2 * n - 1; i++) { 687 cost[i] += cost[ch[i][0]] + cost[ch[i][1]]; 688 } 689 // (point, slope increase) 690 vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n); 691 vector<int> idx(2 * n - 1); 692 iota(all(idx), 0); 693 for (int i = 0; i < 2 * n - 1; i++) { 694 if (i < n) { 695 pq[i].push({cost[i], 1}); 696 continue; 697 } 698 if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]])) 699 swap(ch[i][0], ch[i][1]); 700 idx[i] = idx[ch[i][0]]; 701 while (sz(pq[idx[ch[i][1]]])) { 702 auto tp = pq[idx[ch[i][1]]].top(); 703 pq[idx[ch[i][1]]].pop(); 704 pq[idx[i]].push(tp); 705 } 706 if (cost[i] >= pq[idx[i]].top()[0]) 707 continue; 708 if (cost[i] >= lint(2e9)) 709 continue; 710 lint A = 0, B = 0; 711 lint pv = -1; 712 while (sz(pq[idx[i]])) { 713 auto [point, slope] = pq[idx[i]].top(); 714 pq[idx[i]].pop(); 715 B += A * (point - pv); 716 pv = point; 717 A += slope; 718 // A x - A * pv + B = x - cost[i] 719 // (A - 1) x = A * pv - B - cost[i] 720 lint U = A * pv - B - cost[i]; 721 lint L = A - 1; 722 // point <= U / L, so no need to dedup 723 if (L > 0) { 724 assert(point * L <= U); 725 if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) { 726 lint f1 = U / L - cost[i]; 727 lint f2 = (U / L + 1 - pv) * A + B; 728 // (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A 729 pq[idx[i]].push({cost[i], 1}); 730 pq[idx[i]].push({U / L, f2 - f1 - 1}); 731 pq[idx[i]].push({U / L + 1, A - (f2 - f1)}); 732 break; 733 } 734 } else if (sz(pq[idx[i]]) == 0) { 735 pq[idx[i]].push({cost[i], 1}); 736 break; 737 } 738 } 739 } 740 int q; 741 cin >> q; 742 vector<pi> queries(q); 743 for (int i = 0; i < q; i++) { 744 cin >> queries[i][0]; 745 queries[i][1] = i; 746 } 747 sort(all(queries)); 748 vector<lint> ans(q); 749 lint A = 0, B = 0, pv = -1; 750 auto T = idx[2 * n - 2]; 751 for (auto &[x, i] : queries) { 752 while (sz(pq[T]) && pq[T].top()[0] <= x) { 753 auto [point, slope] = pq[T].top(); 754 pq[T].pop(); 755 B += A * (point - pv); 756 pv = point; 757 A += slope; 758 } 759 ans[i] = (x - pv) * A + B; 760 } 761 for (auto &v : ans) 762 cout << v << "\n"; 763 } 764 } 765 ```