1693.md (12447B)
1 Source: https://codeforces.com/blog/entry/103952 2 3 ### [1694A - Жуть](/contest/1694/problem/A "Codeforces Round 800 (Div. 2)") 4 5 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Implementation** 12 13 ``` 14 # include <bits/stdc++.h> 15 16 using namespace std; 17 18 int t, A, B; 19 20 int main(){ 21 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 22 23 cin >> t; 24 while (t --){ 25 cin >> A >> B; 26 for (int i = 0; i < min(A, B); ++ i) 27 cout << "01"; 28 for (int i = 0; i < abs(A - B); ++ i) 29 cout << (A < B ? 1 : 0); 30 cout << '\n'; 31 } 32 33 return 0; 34 } 35 ``` 36 37 ### [1694B - Параноидальная строка](/contest/1694/problem/B "Codeforces Round 800 (Div. 2)") 38 39 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ") 40 41 **Solution** 42 43 Tutorial is loading... 44 45 **Implementation** 46 47 ``` 48 # include <bits/stdc++.h> 49 50 using namespace std; 51 52 int t, n; 53 string S; 54 long long ans; 55 56 int main(){ 57 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 58 59 cin >> t; 60 while (t --){ 61 cin >> n >> S, ans = n; 62 for (int i = 1; i < n; ++ i) 63 if (S[i] != S[i - 1]) 64 ans += i; 65 cout << ans << '\n'; 66 } 67 68 return 0; 69 } 70 ``` 71 72 ### [1693A - Ориентированное увеличение](/contest/1693/problem/A "Codeforces Round 800 (Div. 1)") 73 74 Idea: [alireza_kaviani](/profile/alireza_kaviani "Гроссмейстер alireza_kaviani") 75 76 **Solution** 77 78 Tutorial is loading... 79 80 **Implementation** 81 82 ``` 83 //In the name of God 84 #include <bits/stdc++.h> 85 using namespace std; 86 87 const int maxn = 2e5 + 100; 88 89 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 90 91 int n, t, a[maxn]; 92 long long ps[maxn]; 93 94 int main(){ 95 fast_io; 96 97 cin >> t; 98 while(t--){ 99 cin >> n; 100 for(int i = 1; i <= n; i++){ 101 cin >> a[i]; 102 ps[i] = ps[i - 1] + a[i]; 103 } 104 if(ps[n] != 0){ 105 cout << "No\n"; 106 continue; 107 } 108 bool ok = 1; 109 for(int i = 1; i <= n; i++){ 110 if(ps[i] < 0) ok = 0; 111 } 112 bool visited_zero = 0; 113 for(int i = 1; i <= n; i++){ 114 if(ps[i] == 0) visited_zero = 1; 115 else if(visited_zero) ok = 0; 116 } 117 if(ok) cout << "Yes\n"; 118 else cout << "No\n"; 119 } 120 121 return 0; 122 } 123 ``` 124 125 ### [1693B - Фейковые пластиковые деревья](/contest/1693/problem/B "Codeforces Round 800 (Div. 1)") 126 127 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ"), [alireza_kaviani](/profile/alireza_kaviani "Гроссмейстер alireza_kaviani") 128 129 **Solution** 130 131 Tutorial is loading... 132 133 **Implementation** 134 135 ``` 136 # include <bits/stdc++.h> 137 138 using namespace std; 139 140 typedef long long ll; 141 142 const int N = 2e5 + 10; 143 144 int t, n, l[N], r[N], ans; 145 vector <int> adj[N]; 146 147 ll DFS(int v){ 148 ll sum = 0; 149 for (int u : adj[v]){ 150 sum += DFS(u); 151 } 152 if (sum < ll(l[v])){ 153 ++ ans; 154 return r[v]; 155 } 156 return min(ll(r[v]), sum); 157 } 158 159 int main(){ 160 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 161 162 cin >> t; 163 while (t --){ 164 cin >> n; 165 for (int i = 2; i <= n; ++ i){ 166 int par; 167 cin >> par; 168 adj[par].push_back(i); 169 } 170 for (int i = 1; i <= n; ++ i){ 171 cin >> l[i] >> r[i]; 172 } 173 ans = 0; 174 DFS(1); 175 cout << ans << "\n"; 176 for (int i = 1; i <= n; ++ i){ 177 adj[i].clear(); 178 } 179 } 180 181 return 0; 182 } 183 ``` 184 185 ### [1693C - Keshi ищет AmShZ](/contest/1693/problem/C "Codeforces Round 800 (Div. 1)") 186 187 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ") 188 189 **Solution** 190 191 Tutorial is loading... 192 193 **Implementation** 194 195 ``` 196 # include <bits/stdc++.h> 197 198 using namespace std; 199 200 const int N = 2e5 + 10; 201 202 int n, m, d[N], dist[N]; 203 priority_queue <pair <int, int> > pq; 204 vector <int> adj[N]; 205 bool mark[N]; 206 207 int main(){ 208 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 209 210 cin >> n >> m; 211 fill(dist, dist + n + 1, m); 212 while (m --){ 213 int v, u; 214 cin >> v >> u; 215 adj[u].push_back(v); 216 ++ d[v]; 217 } 218 dist[n] = 0; 219 pq.push({0, n}); 220 while (!pq.empty()){ 221 int v = pq.top().second; 222 pq.pop(); 223 if (mark[v]) 224 continue; 225 mark[v] = true; 226 for (int u : adj[v]){ 227 if (dist[v] + d[u] < dist[u]){ 228 dist[u] = dist[v] + d[u]; 229 pq.push({- dist[u], u}); 230 } 231 -- d[u]; 232 } 233 } 234 cout << dist[1] << '\n'; 235 236 return 0; 237 } 238 ``` 239 240 ### [1693D - Разбиение на возрастающую и спадающую](/contest/1693/problem/D "Codeforces Round 800 (Div. 1)") 241 242 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ") 243 244 **Solution 1** 245 246 Tutorial is loading... 247 248 Thanks to [Koosha_Mv](/profile/Koosha_Mv "Гроссмейстер Koosha_Mv") 249 250 **Solution 2** 251 252 It can be proven that a permutation is **Decinc** if and only if it's $3412$-avoiding and $2143$-avoiding. 253 254 **Implementation 1** 255 256 ``` 257 # include <bits/stdc++.h> 258 259 using namespace std; 260 261 const int N = 2e5 + 10; 262 263 int n, a[N], dp[N], pd[N], f[N]; 264 long long ans; 265 266 inline void upd(int i){ 267 if (n < i) 268 return; 269 int inc = 0, dec = n + 1; 270 if (pd[i - 1] < a[i]) 271 inc = max(inc, a[i - 1]); 272 if (a[i - 1] < a[i]) 273 inc = max(inc, dp[i - 1]); 274 if (a[i] < dp[i - 1]) 275 dec = min(dec, a[i - 1]); 276 if (a[i] < a[i - 1]) 277 dec = min(dec, pd[i - 1]); 278 if (inc == dp[i] && dec == pd[i]) 279 return; 280 dp[i] = inc, pd[i] = dec; 281 f[i] = 0; 282 if (dec <= n || inc){ 283 upd(i + 1); 284 f[i] = f[i + 1] + 1; 285 } 286 return; 287 } 288 289 int main(){ 290 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 291 292 cin >> n; 293 for (int i = 1; i <= n; ++ i) 294 cin >> a[i]; 295 for (int i = n; 1 <= i; -- i){ 296 dp[i] = n + 1; 297 pd[i] = 0; 298 upd(i + 1); 299 f[i] = f[i + 1] + 1; 300 ans += f[i]; 301 } 302 cout << ans << '\n'; 303 304 return 0; 305 } 306 ``` 307 308 **Implementation 2** 309 310 ``` 311 # include <bits/stdc++.h> 312 313 using namespace std; 314 315 const int N = 2e5 + 10; 316 317 int n, a[N], min_r[N], fen[N]; 318 long long ans; 319 stack <int> sk; 320 vector <int> vec[2][N]; 321 322 void mofen(int pos, int val){ 323 for (pos += 5; pos < N; pos += pos & - pos) 324 fen[pos] = min(fen[pos], val); 325 } 326 int gefen(int pos){ 327 int res = n + 1; 328 for (pos += 5; 0 < pos; pos -= pos & - pos) 329 res = min(res, fen[pos]); 330 return res; 331 } 332 333 void find_3412(){ 334 fill(fen, fen + n + 10, n + 1); 335 while (!sk.empty()) 336 sk.pop(); 337 for (int i = 1; i <= n; ++ i){ 338 while (!sk.empty() && a[i] < a[sk.top()]) 339 sk.pop(); 340 if (!sk.empty()) 341 vec[0][sk.top()].push_back(i); 342 sk.push(i); 343 } 344 while (!sk.empty()) 345 sk.pop(); 346 for (int i = n; 1 <= i; -- i){ 347 while (!sk.empty() && a[sk.top()] < a[i]) 348 sk.pop(); 349 if (!sk.empty()) 350 vec[1][sk.top()].push_back(i); 351 sk.push(i); 352 } 353 for (int i = n; 1 <= i; -- i){ 354 for (int ind : vec[0][i]) 355 mofen(a[ind], ind); 356 for (int ind : vec[1][i]) 357 min_r[ind] = min(min_r[ind], gefen(a[ind] - 1)); 358 vec[0][i].clear(), vec[1][i].clear(); 359 } 360 } 361 362 int main(){ 363 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 364 365 cin >> n; 366 for (int i = 1; i <= n; ++ i) 367 cin >> a[i]; 368 fill(min_r, min_r + n + 2, n + 1); 369 find_3412(); 370 for (int i = 1; i <= n; ++ i) 371 a[i] = n + 1 - a[i]; 372 find_3412(); 373 for (int i = n; 1 <= i; -- i){ 374 min_r[i] = min(min_r[i], min_r[i + 1]); 375 ans += min_r[i] - i; 376 } 377 cout << ans << '\n'; 378 379 return 0; 380 } 381 ``` 382 383 ### [1693E - Крайние максимумы](/contest/1693/problem/E "Codeforces Round 800 (Div. 1)") 384 385 Idea: [Keshi](/profile/Keshi "Гроссмейстер Keshi") 386 387 **Solution** 388 389 Tutorial is loading... 390 391 **Implementation** 392 393 ``` 394 //In the name of God 395 #include <bits/stdc++.h> 396 using namespace std; 397 398 typedef long long ll; 399 typedef pair<int, int> pii; 400 typedef pair<ll, ll> pll; 401 402 const ll maxn = 2e5 + 100; 403 const ll mod = 1e9 + 7; 404 const int inf = 1e9; 405 const ll INF = 1e18; 406 407 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 408 #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); 409 #define pb push_back 410 #define Mp make_pair 411 #define F first 412 #define S second 413 #define Sz(x) ll((x).size()) 414 #define all(x) (x).begin(), (x).end() 415 #define lc (id << 1) 416 #define rc (lc | 1) 417 418 ll pw(ll a, ll b){ 419 ll c = 1; 420 while(b){ 421 if(b & 1) c = c * a % mod; 422 a = a * a % mod; 423 b >>= 1; 424 } 425 return c; 426 } 427 428 struct cost{ 429 int c[2][2]; 430 cost(){ 431 memset(c, 0, sizeof c); 432 } 433 }; 434 435 cost cst[2][2]; 436 437 int n, a[maxn], dp[maxn], cnl[maxn], cnr[maxn]; 438 ll s, ans, ans2; 439 cost seg[maxn << 2]; 440 441 inline cost mrg(cost l, cost r){ 442 cost mid; 443 for(int i = 0; i < 2; i++){ 444 for(int j = 0; j < 2; j++){ 445 mid.c[i][j] = min(r.c[i][0] + l.c[0][j], r.c[i][1] + l.c[1][j]); 446 } 447 } 448 return mid; 449 } 450 451 void bld(int id, int s, int e){ 452 if(e - s == 1){ 453 seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)]; 454 return; 455 } 456 int mid = (s + e) >> 1; 457 bld(lc, s, mid); 458 bld(rc, mid, e); 459 seg[id] = mrg(seg[lc], seg[rc]); 460 return; 461 } 462 463 void upd(int id, int s, int e, int l, int r){ 464 if(r <= s || e <= l) return; 465 if(l <= s && e <= r){ 466 seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)]; 467 return; 468 } 469 int mid = (s + e) >> 1; 470 upd(lc, s, mid, l, r); 471 upd(rc, mid, e, l, r); 472 seg[id] = mrg(seg[lc], seg[rc]); 473 return; 474 } 475 cost get(int id, int s, int e, int l, int r){ 476 if(r <= s || e <= l) return cost(); 477 if(l <= s && e <= r) return seg[id]; 478 int mid = (s + e) >> 1; 479 return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r)); 480 } 481 482 int main(){ 483 fast_io; 484 srand(time(NULL)); 485 486 cst[0][0].c[0][0] = cst[0][0].c[1][1] = 0; 487 cst[0][0].c[0][1] = cst[0][0].c[1][0] = inf; 488 489 cst[0][1].c[1][0] = cst[0][1].c[1][1] = 1; 490 cst[0][1].c[0][0] = 0; 491 cst[0][1].c[0][1] = inf; 492 493 cst[1][0].c[0][1] = cst[1][0].c[0][0] = 1; 494 cst[1][0].c[1][1] = 0; 495 cst[1][0].c[1][0] = inf; 496 497 cst[1][1].c[0][0] = cst[1][1].c[1][1] = 1; 498 cst[1][1].c[0][1] = cst[1][1].c[1][0] = 1; 499 500 cin >> n; 501 cnr[0] = cnl[0] = 1; 502 for(int i = 1; i <= n; i++){ 503 cin >> a[i]; 504 cnr[a[i]]++; 505 s += a[i]; 506 } 507 bld(1, 0, n + 1); 508 for(int i = 1; i <= n; i++){ 509 cost cs = get(1, 0, n + 1, 0, a[i]); 510 cnr[a[i]]--; 511 cnl[a[i]]++; 512 upd(1, 0, n + 1, a[i], a[i] + 1); 513 dp[i] = min({cs.c[0][0], cs.c[0][1], cs.c[1][0], cs.c[1][1]}); 514 ans += dp[i]; 515 } 516 517 cout << ans << "\n"; 518 519 return 0; 520 } 521 ``` 522 523 Check out [this](https://codeforces.com/blog/entry/103952?#comment-923531) solution by [ecnerwala](/profile/ecnerwala "Легендарный гроссмейстер ecnerwala") 524 525 ### [1693F - Я могу ошибаться](/contest/1693/problem/F "Codeforces Round 800 (Div. 1)") 526 527 Idea: [AmShZ](/profile/AmShZ "Гроссмейстер AmShZ") 528 529 Thanks to [antontrygubO_o](/profile/antontrygubO_o "Международный гроссмейстер antontrygubO_o") for proof 530 531 **Solution** 532 533 Tutorial is loading... 534 535 **Implementation by Um_nik** 536 537 ``` 538 #include <iostream> 539 #include <cstdio> 540 #include <cstdlib> 541 #include <algorithm> 542 #include <cmath> 543 #include <vector> 544 #include <set> 545 #include <map> 546 #include <unordered_set> 547 #include <unordered_map> 548 #include <queue> 549 #include <ctime> 550 #include <cassert> 551 #include <complex> 552 #include <string> 553 #include <cstring> 554 #include <chrono> 555 #include <random> 556 #include <bitset> 557 #include <array> 558 using namespace std; 559 560 #ifdef LOCAL 561 #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);} 562 #else 563 #define eprintf(...) 42 564 #endif 565 566 using ll = long long; 567 using ld = long double; 568 using uint = unsigned int; 569 using ull = unsigned long long; 570 template<typename T> 571 using pair2 = pair<T, T>; 572 using pii = pair<int, int>; 573 using pli = pair<ll, int>; 574 using pll = pair<ll, ll>; 575 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 576 ll myRand(ll B) { 577 return (ull)rng() % B; 578 } 579 580 #define pb push_back 581 #define mp make_pair 582 #define all(x) (x).begin(),(x).end() 583 #define fi first 584 #define se second 585 586 clock_t startTime; 587 double getCurrentTime() { 588 return (double)(clock() - startTime) / CLOCKS_PER_SEC; 589 } 590 591 const int N = 200200; 592 int n; 593 char s[N]; 594 int bal[N]; 595 int pos[N]; 596 597 void solve() { 598 scanf("%d %s", &n, s); 599 int b = 0; 600 for (int i = 0; i < n; i++) { 601 if (s[i] == '0') 602 b++; 603 else 604 b--; 605 } 606 if (b < 0) { 607 for (int i = 0; i < n; i++) 608 s[i] ^= 1; 609 reverse(s, s + n); 610 b *= -1; 611 } 612 bal[0] = (n + b) / 2; 613 for (int i = 0; i < n; i++) 614 bal[i + 1] = bal[i] + (s[i] == '0' ? -1 : 1); 615 assert(bal[n] == (n - b) / 2); 616 for (int i = 0; i <= n; i++) 617 pos[i] = -1; 618 for (int i = 0; i <= n; i++) 619 pos[bal[i]] = i; 620 int ans = 0; 621 int l = 0; 622 while(l < (n + b) / 2) { 623 if (bal[l + 1] < bal[l]) { 624 l++; 625 continue; 626 } 627 if (bal[l] <= (n - b) / 2) { 628 ans++; 629 break; 630 } 631 int r = pos[bal[l]]; 632 assert(r > l); 633 ans++; 634 for (int i = l + 1; i < r; i++) { 635 if (2 * i > l + r) { 636 bal[i] = bal[l] - (r - i); 637 } else { 638 bal[i] = bal[l] - (i - l); 639 } 640 pos[bal[i]] = max(pos[bal[i]], i); 641 } 642 } 643 printf("%d\n", ans); 644 } 645 646 int main() 647 { 648 startTime = clock(); 649 // freopen("input.txt", "r", stdin); 650 // freopen("output.txt", "w", stdout); 651 int t; 652 scanf("%d", &t); 653 while(t--) solve(); 654 655 return 0; 656 } 657 ``` 658 659 Thanks to [Um_nik](/profile/Um_nik "Легендарный гроссмейстер Um_nik")