1093.md (11597B)
1 Source: https://codeforces.com/blog/entry/63877 2 3 [1093A - Dice Rolling](/contest/1093/problem/A "Educational Codeforces Round 56 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int t; 18 cin >> t; 19 for (int i = 0; i < t; ++i) { 20 int x; 21 cin >> x; 22 cout << x / 2 << endl; 23 } 24 return 0; 25 } 26 ``` 27 28 [1093B - Letters Rearranging](/contest/1093/problem/B "Educational Codeforces Round 56 (Rated for Div. 2)") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (Vovuh)** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 int main() { 42 int t; 43 cin >> t; 44 for (int i = 0; i < t; ++i) { 45 string s; 46 cin >> s; 47 sort(s.begin(), s.end()); 48 if (s[0] == s.back()) cout << -1 << endl; 49 else cout << s << endl; 50 } 51 return 0; 52 } 53 ``` 54 55 [1093C - Mishka and the Last Exam](/contest/1093/problem/C "Educational Codeforces Round 56 (Rated for Div. 2)") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution (PikMike)** 62 63 ``` 64 n = int(input()) 65 l, r = 0, 10**18 66 b = list(map(int, input().split())) 67 a = [0 for i in range(n)] 68 for i in range(n // 2): 69 a[i] = max(l, b[i] - r) 70 a[-i - 1] = b[i] - a[i] 71 l, r = a[i], a[-i - 1] 72 print(*a) 73 ``` 74 75 **Naive (PikMike)** 76 77 ``` 78 #include <bits/stdc++.h> 79 80 #define forn(i, n) for (int i = 0; i < int(n); i++) 81 82 using namespace std; 83 84 const long long INF64 = 1'000'000'000'000'000'000ll; 85 const int N = 200 * 1000 + 13; 86 87 int n; 88 long long a[N], b[N]; 89 90 void brute(int x, long long l, long long r){ 91 if (x == n / 2){ 92 forn(i, n) 93 printf("%lld ", a[i]); 94 puts(""); 95 exit(0); 96 } 97 98 for (long long i = l; i <= b[x] / 2; ++i) if (b[x] - i <= r){ 99 a[x] = i; 100 a[n - x - 1] = b[x] - i; 101 brute(x + 1, i, b[x] - i); 102 } 103 } 104 105 int main() { 106 scanf("%d", &n); 107 forn(i, n / 2) 108 scanf("%lld", &b[i]); 109 brute(0, 0, INF64); 110 return 0; 111 } 112 ``` 113 114 [1093D - Beautiful Graph](/contest/1093/problem/D "Educational Codeforces Round 56 (Rated for Div. 2)") 115 116 **Tutorial** 117 118 Tutorial is loading... 119 120 **Solution (Ajosteen)** 121 122 ``` 123 #include <bits/stdc++.h> 124 125 using namespace std; 126 127 const int N = int(3e5) + 999; 128 const int MOD = 998244353; 129 130 int n, m; 131 vector <int> g[N]; 132 int p2[N]; 133 int cnt[2]; 134 int col[N]; 135 bool bad; 136 137 void dfs(int v, int c){ 138 col[v] = c; 139 ++cnt[c]; 140 for(auto to : g[v]){ 141 if(col[to] == -1) dfs(to, 1 - c); 142 if((col[v] ^ col[to]) == 0) 143 bad = true; 144 } 145 } 146 147 int main() { 148 p2[0] = 1; 149 for(int i = 1; i < N; ++i) 150 p2[i] = (2 * p2[i - 1]) % MOD; 151 152 int tc; 153 scanf("%d", &tc); 154 while(tc--){ 155 scanf("%d%d", &n, &m); 156 for(int i = 0; i < n; ++i) 157 g[i].clear(); 158 159 for(int i = 0; i < m; ++i){ 160 int u, v; 161 scanf("%d %d", &u, &v); 162 --u, --v; 163 g[u].push_back(v); 164 g[v].push_back(u); 165 } 166 167 int res = 1; 168 for(int i = 0; i < n; ++i) col[i] = -1; 169 for(int i = 0; i < n; ++i){ 170 if(col[i] != -1) continue; 171 bad = false; 172 cnt[0] = cnt[1] = 0; 173 dfs(i, 0); 174 if(bad){ 175 puts("0"); 176 break; 177 } 178 int cur = (p2[cnt[0]] + p2[cnt[1]]) % MOD; 179 res = (res * 1LL * cur) % MOD; 180 } 181 182 if(!bad) printf("%d\n", res); 183 } 184 185 return 0; 186 } 187 ``` 188 189 [1093E - Intersection of Permutations](/contest/1093/problem/E "Educational Codeforces Round 56 (Rated for Div. 2)") 190 191 **Tutorial** 192 193 Tutorial is loading... 194 195 **Solution (PikMike)** 196 197 ``` 198 #include <bits/stdc++.h> 199 200 #define forn(i, n) for (int i = 0; i < int(n); i++) 201 202 using namespace std; 203 204 const int N = 200 * 1000 + 13; 205 206 int n, m; 207 int a[N], b[N], pos[N]; 208 209 vector<int> f[N]; 210 vector<int> vals[N]; 211 212 void addupd(int x, int y){ 213 for (int i = x; i < N; i |= i + 1) 214 vals[i].push_back(y); 215 } 216 217 void addget(int x, int y){ 218 if (x < 0 || y < 0) return; 219 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 220 vals[i].push_back(y); 221 } 222 223 void upd(int x, int y, int val){ 224 for (int i = x; i < N; i |= i + 1) 225 for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < int(f[i].size()); j |= j + 1) 226 f[i][j] += val; 227 } 228 229 int get(int x, int y){ 230 if (x < 0 || y < 0) return 0; 231 int res = 0; 232 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 233 for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j >= 0; j = (j & (j + 1)) - 1) 234 res += f[i][j]; 235 return res; 236 } 237 238 struct query{ 239 int t, la, ra, lb, rb; 240 query(){}; 241 }; 242 243 query q[N]; 244 245 int main() { 246 scanf("%d%d", &n, &m); 247 248 forn(i, n){ 249 scanf("%d", &a[i]); 250 --a[i]; 251 pos[a[i]] = i; 252 } 253 254 forn(i, n){ 255 scanf("%d", &b[i]); 256 --b[i]; 257 b[i] = pos[b[i]]; 258 } 259 260 forn(i, m){ 261 scanf("%d", &q[i].t); 262 if (q[i].t == 1){ 263 scanf("%d%d%d%d", &q[i].la, &q[i].ra, &q[i].lb, &q[i].rb); 264 --q[i].la, --q[i].ra, --q[i].lb, --q[i].rb; 265 } 266 else{ 267 scanf("%d%d", &q[i].lb, &q[i].rb); 268 --q[i].lb, --q[i].rb; 269 } 270 } 271 272 vector<int> tmp(b, b + n); 273 274 forn(i, n) addupd(i, b[i]); 275 forn(i, m){ 276 if (q[i].t == 1){ 277 addget(q[i].rb, q[i].ra); 278 addget(q[i].lb - 1, q[i].ra); 279 addget(q[i].rb, q[i].la - 1); 280 addget(q[i].lb - 1, q[i].la - 1); 281 } 282 else{ 283 addupd(q[i].lb, b[q[i].lb]); 284 addupd(q[i].rb, b[q[i].rb]); 285 swap(b[q[i].lb], b[q[i].rb]); 286 addupd(q[i].lb, b[q[i].lb]); 287 addupd(q[i].rb, b[q[i].rb]); 288 } 289 } 290 291 forn(i, n) b[i] = tmp[i]; 292 293 forn(i, N){ 294 sort(vals[i].begin(), vals[i].end()); 295 vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin()); 296 f[i].resize(vals[i].size(), 0); 297 } 298 299 forn(i, n) 300 upd(i, b[i], 1); 301 302 forn(i, m){ 303 if (q[i].t == 1){ 304 int res = 0; 305 res += get(q[i].rb, q[i].ra); 306 res -= get(q[i].lb - 1, q[i].ra); 307 res -= get(q[i].rb, q[i].la - 1); 308 res += get(q[i].lb - 1, q[i].la - 1); 309 printf("%d\n", res); 310 } 311 else{ 312 upd(q[i].lb, b[q[i].lb], -1); 313 upd(q[i].rb, b[q[i].rb], -1); 314 swap(b[q[i].lb], b[q[i].rb]); 315 upd(q[i].lb, b[q[i].lb], 1); 316 upd(q[i].rb, b[q[i].rb], 1); 317 } 318 } 319 return 0; 320 } 321 ``` 322 323 [1093F - Vasya and Array](/contest/1093/problem/F "Educational Codeforces Round 56 (Rated for Div. 2)") 324 325 **Tutorial** 326 327 Tutorial is loading... 328 329 **Solution (Ajosteen)** 330 331 ``` 332 #include <bits/stdc++.h> 333 334 #define fore(i, l, r) for(int i = int(l); i < int(r); ++i) 335 #define forn(i, n) fore(i, 0, n) 336 #define nfor(i, n) for(int i = int(n) - 1; i >= 0; --i) 337 #define for1(i, n) for(int i = 1; i < int(n); ++i) 338 339 #define mp make_pair 340 #define pb push_back 341 #define sz(a) int((a).size()) 342 #define all(a) (a).begin(), (a).end() 343 #define x first 344 #define y second 345 346 #define correct(x, y, xmax, ymax) ((x) >= 0 && (x) < (xmax) && (y) >= 0 && (y) < (ymax)) 347 #define max(a, b) ((a > b)? a : b) 348 #define min(a, b) ((a < b)? a : b) 349 #define abs(a) ((a < 0) ? -a : a) 350 #define sqr(a) (a * a) 351 352 using namespace std; 353 354 const int N = int(1e5); 355 const int M = 105; 356 const int MOD = 998244353; 357 358 int sum(int a, int b){ 359 return (a + b) % MOD; 360 } 361 362 int n, k, len; 363 int a[N]; 364 int dp[N][M]; 365 int sumdp[N]; 366 int cnt[M][N]; 367 368 int main() { 369 scanf("%d %d %d", &n, &k, &len); 370 forn(i, n){ 371 scanf("%d", a + i); 372 if(a[i] != -1) --a[i]; 373 } 374 forn(i, k) 375 forn(j, n) 376 cnt[i][j + 1] = cnt[i][j] + (a[j] == i || a[j] == -1); 377 378 forn(i, n){ 379 forn(j, k){ 380 if(!(a[i] == -1 || a[i] == j)) 381 continue; 382 383 int add = 1; 384 if(i > 0) add = sumdp[i - 1]; 385 dp[i][j] = add; 386 387 bool ok = i + 1 >= len; 388 int l = max(0, i - len + 1); 389 int r = i + 1; 390 ok &= (r - l == cnt[j][r] - cnt[j][l]); 391 if(!ok) continue; 392 393 if(i + 1 == len){ 394 dp[i][j] = sum(dp[i][j], MOD - 1); 395 continue; 396 } 397 398 add = sum(dp[i - len][j], MOD - sumdp[i - len]); 399 dp[i][j] = sum(dp[i][j], add); 400 } 401 forn(j, k) sumdp[i] = sum(sumdp[i], dp[i][j]); 402 } 403 404 printf("%d\n", sumdp[n - 1]); 405 406 return 0; 407 } 408 ``` 409 410 [1093G - Multidimensional Queries](/contest/1093/problem/G "Educational Codeforces Round 56 (Rated for Div. 2)") 411 412 **Tutorial** 413 414 Tutorial is loading... 415 416 **Solution (BledDest)** 417 418 ``` 419 #include <bits/stdc++.h> 420 421 using namespace std; 422 423 const int N = 200043; 424 const int INF = int(1e9); 425 426 int T[4 * N][32]; 427 int A[4 * N][5]; 428 int n, k; 429 430 void build(int v, int l, int r) 431 { 432 if(l == r - 1) 433 { 434 for(int i = 0; i < (1 << k); i++) 435 { 436 int cur = 0; 437 for(int j = 0; j < k; j++) 438 if(i & (1 << j)) 439 cur += A[l][j]; 440 else 441 cur -= A[l][j]; 442 T[v][i] = cur; 443 } 444 } 445 else 446 { 447 int m = (l + r) / 2; 448 build(v * 2 + 1, l, m); 449 build(v * 2 + 2, m, r); 450 for(int i = 0; i < (1 << k); i++) 451 T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]); 452 } 453 } 454 455 int query(int v, int l, int r, int L, int R, int x) 456 { 457 if(L >= R) return INF; 458 if(L == l && R == r) 459 return T[v][x]; 460 int m = (l + r) / 2; 461 return min(query(v * 2 + 1, l, m, L, min(R, m), x), query(v * 2 + 2, m, r, max(L, m), R, x)); 462 } 463 464 void upd(int v, int l, int r, int z) 465 { 466 if(l == r - 1) 467 { 468 for(int i = 0; i < (1 << k); i++) 469 { 470 int cur = 0; 471 for(int j = 0; j < k; j++) 472 if(i & (1 << j)) 473 cur += A[l][j]; 474 else 475 cur -= A[l][j]; 476 T[v][i] = cur; 477 } 478 } 479 else 480 { 481 int m = (l + r) / 2; 482 if(z < m) 483 upd(v * 2 + 1, l, m, z); 484 else 485 upd(v * 2 + 2, m, r, z); 486 for(int i = 0; i < (1 << k); i++) 487 T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]); 488 } 489 } 490 491 int main() 492 { 493 scanf("%d %d", &n, &k); 494 for(int i = 0; i < n; i++) 495 { 496 for(int j = 0; j < k; j++) 497 { 498 scanf("%d", &A[i][j]); 499 } 500 } 501 int q; 502 scanf("%d", &q); 503 build(0, 0, n); 504 for(int i = 0; i < q; i++) 505 { 506 int t; 507 scanf("%d", &t); 508 if(t == 1) 509 { 510 int z; 511 scanf("%d", &z); 512 --z; 513 for(int j = 0; j < k; j++) 514 scanf("%d", &A[z][j]); 515 upd(0, 0, n, z); 516 } 517 else 518 { 519 int ans = 0; 520 int l, r; 521 scanf("%d %d", &l, &r); 522 --l; 523 for(int i = 0; i < (1 << (k - 1)); i++) 524 { 525 int x = query(0, 0, n, l, r, i); 526 int y = query(0, 0, n, l, r, ((1 << k) - 1) ^ i); 527 ans = max(ans, abs(x + y)); 528 } 529 printf("%d\n", ans); 530 } 531 } 532 return 0; 533 } 534 ``` 535 536 **Solution (PikMike)** 537 538 ``` 539 #include <bits/stdc++.h> 540 541 #define forn(i, n) for (int i = 0; i < int(n); i++) 542 543 using namespace std; 544 545 const int N = 200 * 1000 + 13; 546 const int INF = 1e9; 547 548 struct point{ 549 int a[5]; 550 point(){}; 551 int& operator[](int x){ 552 return a[x]; 553 } 554 }; 555 556 int n, k; 557 point a[N]; 558 559 int t[32][4 * N]; 560 561 int apply(point& p, int mask){ 562 int res = 0; 563 forn(i, k){ 564 res += (mask & 1 ? p[i] : -p[i]); 565 mask >>= 1; 566 } 567 return res; 568 } 569 570 void build(int v, int l, int r){ 571 if (l == r - 1){ 572 forn(mask, 1 << k) 573 t[mask][v] = apply(a[l], mask); 574 return; 575 } 576 577 int m = (l + r) / 2; 578 579 build(v * 2, l, m); 580 build(v * 2 + 1, m, r); 581 582 forn(mask, 1 << k) 583 t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]); 584 } 585 586 void upd(int v, int l, int r, int pos, point& val){ 587 if (l == r - 1){ 588 forn(mask, 1 << k) 589 t[mask][v] = apply(val, mask); 590 return; 591 } 592 593 int m = (l + r) / 2; 594 595 if (pos < m) 596 upd(v * 2, l, m, pos, val); 597 else 598 upd(v * 2 + 1, m, r, pos, val); 599 600 forn(mask, 1 << k) 601 t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]); 602 } 603 604 int bst[32]; 605 606 void get(int v, int l, int r, int L, int R){ 607 if (L >= R) 608 return; 609 610 if (l == L && r == R){ 611 forn(mask, 1 << k) 612 bst[mask] = min(bst[mask], t[mask][v]); 613 return; 614 } 615 616 int m = (l + r) / 2; 617 618 get(v * 2, l, m, L, min(m, R)); 619 get(v * 2 + 1, m, r, max(m, L), R); 620 } 621 622 int main() { 623 scanf("%d%d", &n, &k); 624 forn(i, n) forn(j, k) 625 scanf("%d", &a[i][j]); 626 build(1, 0, n); 627 628 int m; 629 scanf("%d", &m); 630 forn(_, m){ 631 int t; 632 scanf("%d", &t); 633 if (t == 1){ 634 int i; 635 scanf("%d", &i); 636 --i; 637 point tmp; 638 forn(j, k) 639 scanf("%d", &tmp[j]); 640 upd(1, 0, n, i, tmp); 641 } 642 else{ 643 int l, r; 644 scanf("%d%d", &l, &r); 645 --l, --r; 646 forn(mask, 1 << k) 647 bst[mask] = INF; 648 get(1, 0, n, l, r + 1); 649 650 int ans = 0; 651 forn(mask, 1 << k) 652 ans = max(ans, abs(bst[(1 << k) - 1 - mask] + bst[mask])); 653 printf("%d\n", ans); 654 } 655 } 656 return 0; 657 } 658 ```