1550.md (11056B)
1 Source: https://codeforces.com/blog/entry/92864 2 3 [1550A - Find The Array](/contest/1550/problem/A "Educational Codeforces Round 111 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 def maxSum(x): 15 return x ** 2 16 17 def getAns(x): 18 res = 1 19 while maxSum(res) < x: 20 res += 1 21 return res 22 23 def main(): 24 t = int(input()) 25 for i in range(t): 26 print(getAns(int(input()))) 27 28 main() 29 ``` 30 31 [1550B - Maximum Cost Deletion](/contest/1550/problem/B "Educational Codeforces Round 111 (Rated for Div. 2)") 32 33 Idea: [Neon](/profile/Neon "Candidate Master Neon") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (Neon)** 40 41 ``` 42 #include <bits/stdc++.h> 43 44 using namespace std; 45 46 int main() { 47 int t; 48 cin >> t; 49 while (t--) { 50 int n, a, b; 51 string s; 52 cin >> n >> a >> b >> s; 53 int m = unique(s.begin(), s.end()) - s.begin(); 54 cout << n * a + max(n * b, (m / 2 + 1) * b) << '\n'; 55 } 56 } 57 ``` 58 59 [1550C - Manhattan Subarrays](/contest/1550/problem/C "Educational Codeforces Round 111 (Rated for Div. 2)") 60 61 Idea: [adedalic](/profile/adedalic "International Master adedalic") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution (adedalic)** 68 69 ``` 70 #include<bits/stdc++.h> 71 72 using namespace std; 73 74 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 75 #define sz(a) int((a).size()) 76 77 #define x first 78 #define y second 79 80 typedef long long li; 81 typedef long double ld; 82 typedef pair<li, li> pt; 83 84 const int INF = int(1e9); 85 const li INF64 = li(1e18); 86 const ld EPS = 1e-9; 87 88 int n; 89 vector<li> a; 90 91 inline bool read() { 92 if(!(cin >> n)) 93 return false; 94 a.resize(n); 95 fore (i, 0, n) 96 cin >> a[i]; 97 return true; 98 } 99 100 li d(const pt &a, const pt &b) { 101 return abs(a.x - b.x) + abs(a.y - b.y); 102 } 103 104 inline void solve() { 105 li ans = 0; 106 fore (i, 0, n) { 107 fore (j, i, n) { 108 if (i + 2 <= j) { 109 bool ok = true; 110 fore (i1, i, j) fore (i2, i1 + 1, j) { 111 if (d(pt(a[i1], i1), pt(a[j], j)) == d(pt(a[i1], i1), pt(a[i2], i2)) + d(pt(a[i2], i2), pt(a[j], j))) 112 ok = false; 113 } 114 if (!ok) 115 break; 116 } 117 ans++; 118 } 119 } 120 cout << ans << endl; 121 } 122 123 int main() { 124 #ifdef _DEBUG 125 freopen("input.txt", "r", stdin); 126 int tt = clock(); 127 #endif 128 ios_base::sync_with_stdio(false); 129 cin.tie(0), cout.tie(0); 130 cout << fixed << setprecision(15); 131 132 int t; cin >> t; 133 134 while(t--) { 135 read(); 136 solve(); 137 138 #ifdef _DEBUG 139 cerr << "TIME = " << clock() - tt << endl; 140 tt = clock(); 141 #endif 142 } 143 return 0; 144 } 145 ``` 146 147 [1550D - Excellent Arrays](/contest/1550/problem/D "Educational Codeforces Round 111 (Rated for Div. 2)") 148 149 Idea: [adedalic](/profile/adedalic "International Master adedalic") 150 151 **Tutorial** 152 153 Tutorial is loading... 154 155 **Solution (adedalic)** 156 157 ``` 158 #include<bits/stdc++.h> 159 160 using namespace std; 161 162 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 163 #define sz(a) int((a).size()) 164 165 const int MOD = int(1e9) + 7; 166 167 int norm(int a) { 168 while (a >= MOD) 169 a -= MOD; 170 while (a < 0) 171 a += MOD; 172 return a; 173 } 174 int mul(int a, int b) { 175 return int(a * 1ll * b % MOD); 176 } 177 int binPow(int a, int k) { 178 int ans = 1; 179 while (k > 0) { 180 if (k & 1) 181 ans = mul(ans, a); 182 a = mul(a, a); 183 k >>= 1; 184 } 185 return ans; 186 } 187 188 const int N = 200 * 1000 + 55; 189 int f[N], inf[N]; 190 191 void precalc() { 192 f[0] = inf[0] = 1; 193 fore (i, 1, N) { 194 f[i] = mul(f[i - 1], i); 195 inf[i] = binPow(f[i], MOD - 2); 196 } 197 } 198 199 int C(int n, int k) { 200 if (k < 0 || n < k) 201 return 0; 202 return mul(f[n], mul(inf[n - k], inf[k])); 203 } 204 205 int n, l, r; 206 207 inline bool read() { 208 if(!(cin >> n >> l >> r)) 209 return false; 210 return true; 211 } 212 213 inline void solve() { 214 int half = n / 2; 215 int st = min(1 - l, r - n); 216 217 int ans = mul(st, C(n, half)); 218 if (n & 1) 219 ans = norm(ans + mul(st, C(n, half + 1))); 220 221 for (int k = st + 1; ; k++) { 222 int lf = max(1, l + k); 223 int rg = min(n, r - k); 224 225 if (rg + 1 - lf < 0) 226 break; 227 228 ans = norm(ans + C(rg + 1 - lf, half - (lf - 1))); 229 if (n & 1) 230 ans = norm(ans + C(rg + 1 - lf, half + 1 - (lf - 1))); 231 } 232 233 cout << ans << endl; 234 } 235 236 int main() { 237 #ifdef _DEBUG 238 freopen("input.txt", "r", stdin); 239 int tt = clock(); 240 #endif 241 ios_base::sync_with_stdio(false); 242 cin.tie(0), cout.tie(0); 243 cout << fixed << setprecision(15); 244 245 precalc(); 246 int t; cin >> t; 247 while (t--) { 248 read(); 249 solve(); 250 251 #ifdef _DEBUG 252 cerr << "TIME = " << clock() - tt << endl; 253 tt = clock(); 254 #endif 255 } 256 return 0; 257 } 258 ``` 259 260 [1550E - Stringforces](/contest/1550/problem/E "Educational Codeforces Round 111 (Rated for Div. 2)") 261 262 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 263 264 **Tutorial** 265 266 Tutorial is loading... 267 268 **Solution (awoo)** 269 270 ``` 271 #include <bits/stdc++.h> 272 273 #define forn(i, n) for (int i = 0; i < int(n); i++) 274 275 using namespace std; 276 277 int n, k; 278 string s; 279 280 bool check(int d){ 281 vector<int> lst(k, n); 282 vector<vector<int>> pos(n + 1, vector<int>(k, n + 1)); 283 for (int i = n - 1; i >= 0; --i){ 284 if (s[i] != '?'){ 285 lst[s[i] - 'a'] = i; 286 } 287 int cur = n; 288 forn(j, k){ 289 pos[i][j] = (i + d <= cur ? i + d : pos[i + 1][j]); 290 cur = min(cur, lst[j]); 291 } 292 cur = n; 293 for (int j = k - 1; j >= 0; --j){ 294 if (i + d > cur) pos[i][j] = pos[i + 1][j]; 295 cur = min(cur, lst[j]); 296 } 297 } 298 vector<int> dp(1 << k, n + 1); 299 dp[0] = 0; 300 forn(mask, 1 << k) if (dp[mask] < n + 1){ 301 forn(i, k) if (!((mask >> i) & 1)) 302 dp[mask | (1 << i)] = min(dp[mask | (1 << i)], pos[dp[mask]][i]); 303 } 304 return dp[(1 << k) - 1] <= n; 305 } 306 307 int main() { 308 cin >> n >> k; 309 cin >> s; 310 int l = 1, r = n; 311 int res = 0; 312 while (l <= r){ 313 int m = (l + r) / 2; 314 if (check(m)){ 315 res = m; 316 l = m + 1; 317 } 318 else{ 319 r = m - 1; 320 } 321 } 322 cout << res << endl; 323 return 0; 324 } 325 ``` 326 327 [1550F - Jumping Around](/contest/1550/problem/F "Educational Codeforces Round 111 (Rated for Div. 2)") 328 329 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 330 331 **Tutorial** 332 333 Tutorial is loading... 334 335 **Solution 1 (awoo)** 336 337 ``` 338 #include <bits/stdc++.h> 339 340 #define forn(i, n) for (int i = 0; i < int(n); i++) 341 342 using namespace std; 343 344 const int INF = 1e9; 345 346 struct edge2{ 347 int u, w; 348 }; 349 350 vector<vector<edge2>> g; 351 352 struct edge3{ 353 int v, u, w; 354 }; 355 356 bool operator <(const edge3 &a, const edge3 &b){ 357 if (a.w != b.w) 358 return a.w < b.w; 359 if (min(a.v, a.u) != min(b.v, b.u)) 360 return min(a.v, a.u) < min(b.v, b.u); 361 return max(a.v, a.u) < max(b.v, b.u); 362 } 363 364 vector<vector<int>> comps; 365 vector<int> p; 366 367 bool unite(int a, int b){ 368 a = p[a], b = p[b]; 369 if (a == b) return false; 370 if (comps[a].size() < comps[b].size()) swap(a, b); 371 for (int v : comps[b]){ 372 p[v] = a; 373 comps[a].push_back(v); 374 } 375 comps[b].clear(); 376 return true; 377 } 378 379 vector<int> mn; 380 381 void dfs(int v, int p, int d){ 382 mn[v] = d; 383 for (auto e : g[v]) if (e.u != p) 384 dfs(e.u, v, max(d, e.w)); 385 } 386 387 int main() { 388 int n, q, s, d; 389 scanf("%d%d%d%d", &n, &q, &s, &d); 390 --s; 391 vector<int> a(n); 392 forn(i, n) scanf("%d", &a[i]); 393 vector<int> idx(a[n - 1] + 1); 394 forn(i, n) idx[a[i]] = i; 395 comps.resize(n); 396 p.resize(n); 397 forn(i, n) comps[i] = vector<int>(1, i), p[i] = i; 398 g.resize(n); 399 set<int> pos(a.begin(), a.end()); 400 int cnt = n; 401 while (cnt > 1){ 402 vector<edge3> es; 403 for (const vector<int> &comp : comps) if (!comp.empty()){ 404 for (int i : comp) 405 pos.erase(a[i]); 406 edge3 mn = {-1, -1, INF}; 407 for (int i : comp){ 408 for (int dx : {-d, d}){ 409 auto it = pos.lower_bound(a[i] + dx); 410 if (it != pos.end()) 411 mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)}); 412 if (it != pos.begin()){ 413 --it; 414 mn = min(mn, {i, idx[*it], abs(abs(a[i] - *it) - d)}); 415 } 416 } 417 } 418 for (int i : comp) 419 pos.insert(a[i]); 420 assert(mn.v != -1); 421 es.push_back(mn); 422 } 423 for (auto e : es){ 424 if (unite(e.v, e.u)){ 425 --cnt; 426 g[e.v].push_back({e.u, e.w}); 427 g[e.u].push_back({e.v, e.w}); 428 } 429 } 430 } 431 mn.resize(n); 432 dfs(s, -1, 0); 433 forn(_, q){ 434 int i, k; 435 scanf("%d%d", &i, &k); 436 --i; 437 puts(mn[i] <= k ? "Yes" : "No"); 438 } 439 return 0; 440 } 441 ``` 442 443 **Solution 2 (awoo)** 444 445 ``` 446 #include <bits/stdc++.h> 447 448 #define forn(i, n) for (int i = 0; i < int(n); i++) 449 450 using namespace std; 451 452 const int INF = 1e9; 453 454 struct edge2{ 455 int u, w; 456 }; 457 458 vector<vector<edge2>> g; 459 460 struct edge3{ 461 int v, u, w; 462 edge3(){} 463 edge3(int v, int u, int w) : v(v), u(u), w(w) { 464 if (v > u) swap(v, u); 465 } 466 }; 467 468 bool operator <(const edge3 &a, const edge3 &b){ 469 if (a.w != b.w) 470 return a.w < b.w; 471 if (a.v != b.v) 472 return a.v < b.v; 473 return a.u < b.u; 474 } 475 476 vector<int> p, rk; 477 478 int getp(int a){ 479 return a == p[a] ? a : p[a] = getp(p[a]); 480 } 481 482 bool unite(int a, int b){ 483 a = getp(a), b = getp(b); 484 if (a == b) return false; 485 if (rk[a] < rk[b]) swap(a, b); 486 rk[a] += rk[b]; 487 p[b] = a; 488 return true; 489 } 490 491 vector<int> mn; 492 493 void dfs(int v, int p, int d){ 494 mn[v] = d; 495 for (auto e : g[v]) if (e.u != p) 496 dfs(e.u, v, max(d, e.w)); 497 } 498 499 int main() { 500 int n, q, s, d; 501 scanf("%d%d%d%d", &n, &q, &s, &d); 502 --s; 503 vector<int> a(n); 504 forn(i, n) scanf("%d", &a[i]); 505 p.resize(n); 506 rk.resize(n); 507 forn(i, n) rk[i] = 1, p[i] = i; 508 g.resize(n); 509 int cnt = n; 510 int iter = 0; 511 while (cnt > 1){ 512 ++iter; 513 vector<edge3> es(n, edge3(-1, -1, INF)); 514 int j, mn1, mn2; 515 j = 0, mn1 = -1, mn2 = -1; 516 forn(i, n) getp(i); 517 forn(i, n){ 518 while (j < n && a[i] - a[j] > d){ 519 if (mn1 == -1 || p[mn1] == p[j]) 520 mn1 = j; 521 else{ 522 mn2 = mn1; 523 mn1 = j; 524 } 525 ++j; 526 } 527 if (mn1 != -1 && p[mn1] != p[i]){ 528 es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d))); 529 } 530 if (mn2 != -1 && p[mn2] != p[i]){ 531 es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d))); 532 } 533 } 534 j = 0, mn1 = -1, mn2 = -1; 535 forn(i, n){ 536 while (j < n && a[j] - a[i] <= d){ 537 if (mn1 == -1 || p[mn1] == p[j]) 538 mn1 = j; 539 else{ 540 mn2 = mn1; 541 mn1 = j; 542 } 543 ++j; 544 } 545 if (mn1 != -1 && p[mn1] != p[i]){ 546 es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d))); 547 } 548 if (mn2 != -1 && p[mn2] != p[i]){ 549 es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d))); 550 } 551 } 552 j = n - 1, mn1 = -1, mn2 = -1; 553 for (int i = n - 1; i >= 0; --i){ 554 while (j >= 0 && a[j] - a[i] > d){ 555 if (mn1 == -1 || p[mn1] == p[j]) 556 mn1 = j; 557 else{ 558 mn2 = mn1; 559 mn1 = j; 560 } 561 --j; 562 } 563 if (mn1 != -1 && p[mn1] != p[i]){ 564 es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d))); 565 } 566 if (mn2 != -1 && p[mn2] != p[i]){ 567 es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d))); 568 } 569 } 570 j = n - 1, mn1 = -1, mn2 = -1; 571 for (int i = n - 1; i >= 0; --i){ 572 while (j >= 0 && a[i] - a[j] <= d){ 573 if (mn1 == -1 || p[mn1] == p[j]) 574 mn1 = j; 575 else{ 576 mn2 = mn1; 577 mn1 = j; 578 } 579 --j; 580 } 581 if (mn1 != -1 && p[mn1] != p[i]){ 582 es[p[i]] = min(es[p[i]], edge3(mn1, i, abs(abs(a[i] - a[mn1]) - d))); 583 } 584 if (mn2 != -1 && p[mn2] != p[i]){ 585 es[p[i]] = min(es[p[i]], edge3(mn2, i, abs(abs(a[i] - a[mn2]) - d))); 586 } 587 } 588 for (auto e : es) if (e.v != -1){ 589 if (unite(e.v, e.u)){ 590 --cnt; 591 g[e.v].push_back({e.u, e.w}); 592 g[e.u].push_back({e.v, e.w}); 593 } 594 } 595 } 596 mn.resize(n); 597 dfs(s, -1, 0); 598 forn(_, q){ 599 int i, k; 600 scanf("%d%d", &i, &k); 601 --i; 602 puts(mn[i] <= k ? "Yes" : "No"); 603 } 604 return 0; 605 } 606 ```