1401.md (8178B)
1 Source: https://codeforces.com/blog/entry/81700 2 3 Thank you for participating. I hope you enjoyed the contest! 4 5 [1401A - Distance and Axis](/contest/1401/problem/A "Codeforces Round 665 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution Code** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 #define endl '\n' 17 18 using namespace std; 19 20 main() 21 { 22 ios_base::sync_with_stdio(0); 23 cin.tie(0); 24 cout.tie(0); 25 26 int k, n, t; 27 28 cin >> t; 29 for(;t--;) 30 { 31 cin >> n >> k; 32 33 if(n < k) 34 cout << k - n << endl; 35 36 else if(n % 2 == k % 2) 37 cout << 0 << endl; 38 39 else 40 cout << 1 << endl; 41 } 42 43 return 0; 44 } 45 ``` 46 47 **Behind Story** 48 49 After 2 problems got rejected, I made this problem but it has 2D coordinate originally. 50 51 [1401B - Ternary Sequence](/contest/1401/problem/B "Codeforces Round 665 (Div. 2)") 52 53 **Tutorial** 54 55 Tutorial is loading... 56 57 **Solution Code** 58 59 ``` 60 #include<bits/stdc++.h> 61 62 #define endl '\n' 63 64 using namespace std; 65 66 main() 67 { 68 ios_base::sync_with_stdio(0); 69 cin.tie(0); 70 cout.tie(0); 71 72 int t; 73 74 cin >> t; 75 for(;t--;) 76 { 77 int m, sum = 0, x0, x1, x2, y0, y1, y2; 78 79 cin >> x0 >> x1 >> x2 >> y0 >> y1 >> y2; 80 81 m = min(x0, y2); 82 x0 -= m; 83 y2 -= m; 84 85 m = min(x1, y0); 86 x1 -= m; 87 y0 -= m; 88 89 m = min(x2, y1); 90 x2 -= m; 91 y1 -= m; 92 sum += 2 * m; 93 94 sum -= 2 * min(x1, y2); 95 96 cout << sum << endl; 97 } 98 } 99 ``` 100 101 **Behind Story** 102 103 One tester suggested to swap $A$ and $B$ but I and [adedalic](/profile/adedalic "International Master adedalic") thought it is not good idea, so the order didn't changed. 104 105 [1401C - Mere Array](/contest/1401/problem/C "Codeforces Round 665 (Div. 2)") 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution Code** 112 113 ``` 114 #import<bits/stdc++.h> 115 116 #define endl '\n' 117 118 using namespace std; 119 120 int a[100005], b[100005]; 121 main() 122 { 123 ios_base::sync_with_stdio(0); 124 cin.tie(0); 125 cout.tie(0); 126 127 int t; 128 cin >> t; 129 for(;t--;) 130 { 131 int k = 0, m = 1000000000, n; 132 133 cin >> n; 134 135 for(int i = 0; i < n; i++) 136 { 137 cin >> a[i]; 138 b[i] = a[i]; 139 m = min(m, a[i]); 140 } 141 142 sort(b, b + n); 143 144 for(int i = 0; i < n; i++) 145 if(a[i] != b[i] && a[i] % m > 0) 146 k = 1; 147 148 if(k) 149 cout<<"NO"<<endl; 150 else 151 cout<<"YES"<<endl; 152 } 153 } 154 ``` 155 156 **Behind Story** 157 158 Most testers especially liked this problem. 159 160 [1401D - Maximum Distributed Tree](/contest/1401/problem/D "Codeforces Round 665 (Div. 2)") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution Code** 167 168 ``` 169 #include<bits/stdc++.h> 170 171 #define endl '\n' 172 173 using namespace std; 174 175 typedef long long LL; 176 177 struct H{int x, y;}; 178 179 int ii, n; 180 const int q = 1e9 + 7; 181 LL p[100005], pv[100005], vi[100005], w[100005]; 182 H e[200040]; 183 184 int C(H a, H b){return a.x < b.x;} 185 int G(LL a, LL b){return a > b;} 186 187 LL dfs(int v) 188 { 189 LL d = 1; 190 191 vi[v] = 1; 192 193 for(int i = pv[v]; i < pv[v+1]; i++) 194 if(!vi[e[i].y]) 195 d += dfs(e[i].y); 196 197 w[ii] = d * (n - d); 198 ii++; 199 200 return d; 201 } 202 203 main() 204 { 205 ios_base::sync_with_stdio(0); 206 cin.tie(0); 207 cout.tie(0); 208 209 int t; 210 211 cin >> t; 212 213 for(;t--;) 214 { 215 int k = 0, m; 216 LL x = 1; 217 218 cin >> n; 219 220 for(int i = 0; i < n - 1; i++) 221 { 222 cin >> e[i].x >> e[i].y; 223 e[i + n - 1].x = e[i].y; 224 e[i + n - 1].y = e[i].x; 225 } 226 227 int sz = 2 * n - 2; 228 229 sort(e, e + sz, C); 230 231 for(int i = 1; i < sz; i++) 232 { 233 if(e[i].x > e[i - 1].x) 234 { 235 for(int j = e[i - 1].x + 1; j <= e[i].x; j++) 236 pv[j] = i; 237 } 238 } 239 for(int j = e[sz - 1].x + 1; j <= n + 2; j++) 240 pv[j] = sz; 241 242 ii = k = 0; 243 dfs(1); 244 245 cin >> m; 246 247 for(int i = 0; i < m; i++) 248 cin >> p[i]; 249 250 sort(p, p + m, G); 251 sort(w, w + n - 1, G); 252 253 if(m < n) 254 for(int i = m; i < n - 1; i++) 255 p[i] = 1; 256 else 257 { 258 int i; 259 260 for(i = m - 1; i > m - n; k = i, i--) 261 w[i] = w[i - m + n - 1]; 262 263 for(; i; i--) 264 w[i] = w[0]; 265 } 266 267 int l = max(m, n - 1); 268 269 int i; 270 for(i = 0, x = w[0]; i <= k; i++) 271 x = x * p[i] % q; 272 273 for(;i < l; i++) 274 x = (x + w[i] * p[i]) % q; 275 276 cout << x << endl; 277 278 for(int i = 1; i <= n; i++) 279 vi[i] = 0; 280 } 281 } 282 ``` 283 284 **Behind Story** 285 286 This problem was inspired by [1187E - Tree Painting](/contest/1187/problem/E "Educational Codeforces Round 67 (Rated for Div. 2)") and [1281E - Jeremy Bearimy](/contest/1281/problem/E "Codeforces Round 607 (Div. 2)"). Originally this was proposed as E, but after some fixing it became more easier than original one. And the modulo was new one originally, but I changed it later by myself. 287 288 [1401E - Divide Square](/contest/1401/problem/E "Codeforces Round 665 (Div. 2)") 289 290 **Tutorial** 291 292 Tutorial is loading... 293 294 **Solution Code** 295 296 ``` 297 #include<bits/stdc++.h> 298 299 using namespace std; 300 301 typedef long long LL; 302 303 struct H{int k, l, r;}; 304 305 const int p = 1048576; 306 307 LL l[2100000], r[2100000], z[2100000]; 308 309 H h[100005], v[200040]; 310 311 int C(H a, H b){return a.k < b.k;} 312 int D(H a, H b){return a.l < b.l || a.l == b.l && a.r > b.r;} 313 314 LL sum(int x, int y, int d) // find the sum of range [x, y] 315 { 316 if(x <= l[d] && r[d] <= y) 317 return z[d]; 318 319 if(x > r[d] || y < l[d]) 320 return 0; 321 322 return sum(x, y, d << 1) + sum(x, y, (d << 1) + 1); 323 } 324 325 void REP(int i, LL k) // add k to i-th number 326 { 327 i += p; 328 329 for(z[i] += k; i >>= 1;) 330 z[i] = z[i << 1] + z[(i << 1) + 1]; 331 } 332 333 main() 334 { 335 ios_base::sync_with_stdio(0); 336 cin.tie(0); 337 cout.tie(0); 338 339 LL m, n, s = 1; 340 341 cin >> n >> m; 342 343 for(int i = 0; i < p; i++) 344 l[i + p] = r[i + p] = i; 345 346 for(int i = p; --i;) 347 { 348 l[i] = l[i << 1]; 349 r[i] = r[(i << 1) + 1]; 350 } 351 352 for(int i = 0; i < n; i++) 353 { 354 cin >> h[i].k >> h[i].l >> h[i].r; 355 356 if(h[i].r - h[i].l == 1000000) 357 s++; 358 } 359 360 sort(h, h + n, C); 361 362 for(int i = 0; i < m; i++) 363 { 364 int j = i << 1; 365 366 cin >> v[j].k >> v[j].l >> v[j+1].l; 367 368 v[j + 1].k = v[j].k; 369 v[j].r = 1; 370 v[j + 1].r = -1; 371 372 if(v[j + 1].l - v[j].l == 1000000) 373 s++; 374 } 375 376 sort(v, v + 2 * m, D); 377 378 for(int i = 0, j = 0; i < n && j < 2 * m;) 379 { 380 if(h[i].k < v[j].l || h[i].k == v[j].l && v[j].r < 0) 381 { 382 s += sum(h[i].l, h[i].r, 1); 383 i++; 384 } 385 else 386 { 387 REP(v[j].k, v[j].r); 388 j++; 389 } 390 } 391 392 cout << s; 393 394 return 0; 395 } 396 ``` 397 398 **Behind Story** 399 400 This problem was inspired by [1075C - The Tower is Going Home](/contest/1075/problem/C "Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)"). Originally the restriction of $n, m$ was small so $O(n^2)$ solution could pass, but [adedalic](/profile/adedalic "International Master adedalic") suggested to increase them up to $10^5$. In fact, I only knew brute forces solution until he tells me the solution using segment tree. And the size of the square was $10^9 \times 10^9$ so coordinate compression would be done additionally, but we eliminated it to avoid too many implementation. 401 402 [1401F - Reverse and Swap](/contest/1401/problem/F "Codeforces Round 665 (Div. 2)") 403 404 **Tutorial** 405 406 Tutorial is loading... 407 408 **Solution Code** 409 410 ``` 411 #include<bits/stdc++.h> 412 413 #define endl '\n' 414 415 using namespace std; 416 417 typedef long long LL; 418 419 LL p, a[528000], ll[528000], rr[528000]; 420 421 LL SUM(LL l, LL r, LL d) 422 { 423 LL x, y, z; 424 425 x = ll[d]; 426 y = rr[d]; 427 z = b & ~(y - x); 428 429 x ^= z; 430 y ^= z; 431 432 if(x > r || y < l) 433 return 0; 434 435 else if(x < l || y > r) 436 return(SUM(l, r, z << 1) + SUM(l, r, (z << 1) + 1)); 437 438 else 439 return a[z]; 440 } 441 442 void REP(LL i,LL k) 443 { 444 i += p; 445 446 for(a[i] = k; i >>= 1;) 447 a[i] = (a[i << 1] + a[(i << 1) + 1]); 448 } 449 450 main() 451 { 452 ios_base::sync_with_stdio(0); 453 cin.tie(0); 454 cout.tie(0); 455 456 int b = 0, i, n, q; 457 458 cin >> n >> q; 459 p = 1 << n; 460 461 for(i = 0; i < p; i++) 462 { 463 cin >> a[p + i]; 464 ll[p + i] = rr[p + i] = i; 465 } 466 467 for(; i < p; i++) 468 ll[p + i] = rr[p + i] = i; 469 470 for(; --i;) 471 { 472 a[i] = (a[i << 1] + a[(i << 1) + 1]); 473 ll[i] = ll[i << 1]; 474 rr[i] = rr[(i << 1) + 1]; 475 } 476 477 for(; q--;) 478 { 479 int m; 480 481 cin >> m; 482 483 if(m == 1) 484 { 485 int k, x; 486 487 cin >> x >> k; 488 489 REP((x - 1) ^ b, k); 490 } 491 492 else if(m == 2) 493 { 494 int k; 495 496 cin >> k; 497 498 b ^= (1 << k) - 1; 499 } 500 501 else if(m == 3) 502 { 503 int k; 504 505 cin >> k; 506 507 b ^= 1 << k; 508 } 509 510 else 511 { 512 int l, r; 513 514 cin >> l >> r; 515 516 cout << SUM(l - 1, r - 1, 1) << endl; 517 } 518 } 519 } 520 ``` 521 522 **Behind Story** 523 524 This problem has 6 generators, and I most liked it among 6 problems.