1946.md (12757B)
1 Source: https://codeforces.com/blog/entry/127439 2 3 author: [dope](/profile/dope "Master dope"), developer: [dope](/profile/dope "Master dope") 4 5 [1946A - Median of an Array](/contest/1946/problem/A "Codeforces Round 936 (Div. 2)") 6 7 **Editorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using i64 = long long; 17 18 void solve() { 19 int n; 20 std::cin >> n; 21 std::vector<int> a(n); 22 for (int i = 0; i < n; i++) { 23 std::cin >> a[i]; 24 } 25 std::sort(a.begin(), a.end()); 26 int p = (n + 1) / 2 - 1; 27 int res = std::count(a.begin() + p, a.end(), a[p]); 28 std::cout << res << "\n"; 29 } 30 31 signed main() { 32 std::ios::sync_with_stdio(false); 33 std::cin.tie(nullptr); 34 35 int t = 1; 36 std::cin >> t; 37 38 while (t--) { 39 solve(); 40 } 41 } 42 ``` 43 44 author: [max0000561](/profile/max0000561 "Master max0000561"), developer: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29") 45 46 [1946B - Maximum Sum](/contest/1946/problem/B "Codeforces Round 936 (Div. 2)") 47 48 **Editorial** 49 50 Tutorial is loading... 51 52 **Solution** 53 54 ``` 55 #include <bits/stdc++.h> 56 using namespace std; 57 #define int long long 58 const int P = 1e9 + 7; 59 60 void solve() { 61 int n, k; 62 cin >> n >> k; 63 vector<int> a(n); 64 for (int i = 0; i < n; i++) 65 cin >> a[i]; 66 int S = 0, sum = 0; 67 int cur = 0; 68 for (int i = 0; i < n; i++) { 69 sum += a[i]; 70 cur += a[i]; 71 cur = max(cur, 0LL); 72 S = max(S, cur); 73 } 74 sum = (sum % P + P) % P; 75 S = S % P; 76 int t = 1; 77 for (int i = 0; i < k; i++) { 78 t = t * 2 % P; 79 } 80 int ans = (sum + S * t - S + P) % P; 81 cout << ans << '\n'; 82 } 83 84 signed main() { 85 //cout << fixed << setprecision(20); 86 ios::sync_with_stdio(false); 87 cin.tie(nullptr); 88 int T = 1, G = 1; 89 //cin >> G; 90 cin >> T; 91 while (T--) 92 solve(); 93 return 0; 94 } 95 ``` 96 97 author: [dope](/profile/dope "Master dope"), developer: [dope](/profile/dope "Master dope") 98 99 [1946C - Tree Cutting](/contest/1946/problem/C "Codeforces Round 936 (Div. 2)") 100 101 **Editorial** 102 103 Tutorial is loading... 104 105 **Solution** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 using i64 = long long; 111 112 void solve() { 113 int n, k; 114 std::cin >> n >> k; 115 std::vector<std::vector<int>> adj(n); 116 for (int i = 0; i < n - 1; i++) { 117 int v, u; 118 std::cin >> v >> u; 119 --v, --u; 120 adj[v].emplace_back(u); 121 adj[u].emplace_back(v); 122 } 123 auto check = [&](int x) { 124 int res = 0; 125 auto dfs = [&](auto self, int v, int f) -> int { 126 int sz = 1; 127 for (int u : adj[v]) { 128 if (u == f) { 129 continue; 130 } 131 sz += self(self, u, v); 132 } 133 if (sz >= x && f != v) { 134 ++res, sz = 0; 135 } 136 return sz; 137 }; 138 int t = dfs(dfs, 0, 0); 139 return (res > k || (t >= x && res == k) ? true : false); 140 }; 141 int low = 1, high = n / (k + 1) + 1; 142 while (high - low > 1) { 143 int mid = (low + high) / 2; 144 if (check(mid)) { 145 low = mid; 146 } else { 147 high = mid; 148 } 149 } 150 std::cout << low << "\n"; 151 } 152 153 signed main() { 154 std::ios::sync_with_stdio(false); 155 std::cin.tie(nullptr); 156 157 int t = 1; 158 std::cin >> t; 159 160 while (t--) { 161 solve(); 162 } 163 } 164 ``` 165 166 author: [sadness](/profile/sadness "Master sadness"), developer: [sadness](/profile/sadness "Master sadness") 167 168 [1946D - Birthday Gift](/contest/1946/problem/D "Codeforces Round 936 (Div. 2)") 169 170 **Editorial** 171 172 Tutorial is loading... 173 174 **Solution** 175 176 ``` 177 #include <bits/stdc++.h> 178 179 using namespace std; 180 181 using ll = long long; 182 183 #define int ll 184 #define all(a) a.begin(), a.end() 185 186 void solve() { 187 int n, x; 188 cin >> n >> x; 189 ++x; 190 vector<int> a(n); 191 for (int &i: a) 192 cin >> i; 193 int res = -1; 194 for (int i = 30; i >= 0; --i) { 195 vector<int> b; 196 bool open = false; 197 for (int j = 0; j < a.size(); ++j) { 198 if (!open) 199 b.push_back(a[j]); 200 else 201 b.back() ^= a[j]; 202 if (a[j] & (1 << i)) 203 open = !open; 204 } 205 if (!(x & (1 << i))) { 206 if (open) { 207 cout << res << '\n'; 208 return; 209 } 210 a = b; 211 } else { 212 if (!open) 213 res = max(res, (int) b.size()); 214 } 215 } 216 cout << res << '\n'; 217 } 218 219 signed main() { 220 ios_base::sync_with_stdio(false); 221 cin.tie(nullptr); 222 int t = 1; 223 cin >> t; 224 while (t--) 225 solve(); 226 } 227 ``` 228 229 **Solution (74TrAkToR)** 230 231 ``` 232 #include<bits/stdc++.h> 233 234 using namespace std; 235 236 int const maxn = 1e5 + 5; 237 int a[maxn]; 238 239 int solve(int n, int x) { 240 int res = 0, curr = 0; 241 for (int i = 1; i <= n; i++) { 242 curr ^= a[i]; 243 if ((curr|x) == x) curr = 0, res++; 244 else { 245 if (i == n) return -1; 246 } 247 } 248 return res; 249 } 250 251 main() { 252 ios_base::sync_with_stdio(0); 253 cin.tie(0); 254 cout.tie(0); 255 int t; 256 cin >> t; 257 while (t--) { 258 int n, x; 259 cin >> n >> x; 260 for (int i = 1; i <= n; i++) cin >> a[i]; 261 int ans = -1; 262 ans = max(ans, solve(n, x)); 263 for (int b = 29; b >= 0; b--) { 264 if ((x>>b)&1) { 265 int y = (x^(1 << b)); 266 for (int c = b - 1; c >= 0; c--) { 267 if (((y>>c)&1) == 0) y ^= (1 << c); 268 } 269 ans = max(ans, solve(n, y)); 270 } 271 } 272 cout << ans << '\n'; 273 } 274 return 0; 275 } 276 ``` 277 278 author: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29"), developer: [yunetive29](/profile/yunetive29 "Candidate Master yunetive29") 279 280 [1946E - Girl Permutation](/contest/1946/problem/E "Codeforces Round 936 (Div. 2)") 281 282 **Editorial** 283 284 Tutorial is loading... 285 286 **Solution** 287 288 ``` 289 #include <bits/stdc++.h> 290 291 using i64 = long long; 292 293 template<class T> 294 constexpr T power(T a, i64 b) { 295 T res = 1; 296 for (; b; b /= 2, a *= a) { 297 if (b % 2) { 298 res *= a; 299 } 300 } 301 return res; 302 } 303 304 template<int P> 305 struct MInt { 306 int x; 307 constexpr MInt() : x{} {} 308 constexpr MInt(i64 x) : x{norm(x % P)} {} 309 310 constexpr int norm(int x) const { 311 if (x < 0) { 312 x += P; 313 } 314 if (x >= P) { 315 x -= P; 316 } 317 return x; 318 } 319 constexpr int val() const { 320 return x; 321 } 322 explicit constexpr operator int() const { 323 return x; 324 } 325 constexpr MInt operator-() const { 326 MInt res; 327 res.x = norm(P - x); 328 return res; 329 } 330 constexpr MInt inv() const { 331 assert(x != 0); 332 return power(*this, P - 2); 333 } 334 constexpr MInt &operator*=(MInt rhs) { 335 x = 1LL * x * rhs.x % P; 336 return *this; 337 } 338 constexpr MInt &operator+=(MInt rhs) { 339 x = norm(x + rhs.x); 340 return *this; 341 } 342 constexpr MInt &operator-=(MInt rhs) { 343 x = norm(x - rhs.x); 344 return *this; 345 } 346 constexpr MInt &operator/=(MInt rhs) { 347 return *this *= rhs.inv(); 348 } 349 friend constexpr MInt operator*(MInt lhs, MInt rhs) { 350 MInt res = lhs; 351 res *= rhs; 352 return res; 353 } 354 friend constexpr MInt operator+(MInt lhs, MInt rhs) { 355 MInt res = lhs; 356 res += rhs; 357 return res; 358 } 359 friend constexpr MInt operator-(MInt lhs, MInt rhs) { 360 MInt res = lhs; 361 res -= rhs; 362 return res; 363 } 364 friend constexpr MInt operator/(MInt lhs, MInt rhs) { 365 MInt res = lhs; 366 res /= rhs; 367 return res; 368 } 369 friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { 370 i64 v; 371 is >> v; 372 a = MInt(v); 373 return is; 374 } 375 friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { 376 return os << a.val(); 377 } 378 friend constexpr bool operator==(MInt lhs, MInt rhs) { 379 return lhs.val() == rhs.val(); 380 } 381 friend constexpr bool operator!=(MInt lhs, MInt rhs) { 382 return lhs.val() != rhs.val(); 383 } 384 }; 385 386 constexpr int MOD = 1e9 + 7; 387 using Z = MInt<MOD>; 388 389 namespace comb { 390 int n = 0; 391 std::vector<Z> _fac = {1}; 392 std::vector<Z> _invfac = {1}; 393 std::vector<Z> _inv = {0}; 394 395 void init(int m) { 396 if (m <= n) return; 397 _fac.resize(m + 1); 398 _invfac.resize(m + 1); 399 _inv.resize(m + 1); 400 401 for (int i = n + 1; i <= m; i++) { 402 _fac[i] = _fac[i - 1] * i; 403 } 404 _invfac[m] = _fac[m].inv(); 405 for (int i = m; i > n; i--) { 406 _invfac[i - 1] = _invfac[i] * i; 407 _inv[i] = _invfac[i] * _fac[i - 1]; 408 } 409 n = m; 410 } 411 412 Z fac(int m) { 413 if (m > n) init(2 * m); 414 return _fac[m]; 415 } 416 Z invfac(int m) { 417 if (m > n) init(2 * m); 418 return _invfac[m]; 419 } 420 Z inv(int m) { 421 if (m > n) init(2 * m); 422 return _inv[m]; 423 } 424 Z binom(int m, int k) { 425 if (m < k || k < 0) return 0; 426 return fac(m) * invfac(k) * invfac(m - k); 427 } 428 } // namespace comb 429 430 void solve() { 431 int n, m1, m2; 432 std::cin >> n >> m1 >> m2; 433 std::vector<int> p(m1), s(m2); 434 for (int i = 0; i < m1; i++) { 435 std::cin >> p[i]; 436 } 437 for (int i = 0; i < m2; i++) { 438 std::cin >> s[i]; 439 } 440 if (p[0] != 1 || s[0] != p[m1 - 1] || s[m2 - 1] != n) { 441 std::cout << "0\n"; 442 return; 443 } 444 Z res = comb::binom(n - 1, s[0] - 1); 445 for (int i = m1 - 2; i > -1; i--) { 446 res *= comb::binom(p[i + 1] - 2, p[i + 1] - p[i] - 1) * comb::fac(p[i + 1] - p[i] - 1); 447 } 448 for (int i = 1; i < m2; i++) { 449 res *= comb::binom(n - s[i - 1] - 1, s[i] - s[i - 1] - 1) * comb::fac(s[i] - s[i - 1] - 1); 450 } 451 std::cout << res << "\n"; 452 } 453 454 signed main() { 455 std::ios::sync_with_stdio(false); 456 std::cin.tie(nullptr); 457 458 #ifndef ONLINE_JUDGE 459 freopen("/home/q1n/coding/input.txt", "r", stdin); 460 freopen("/home/q1n/coding/output.txt", "w", stdout); 461 #else 462 // online submission 463 #endif 464 465 int t = 1; 466 std::cin >> t; 467 468 while (t--) { 469 solve(); 470 } 471 } 472 ``` 473 474 author: [dope](/profile/dope "Master dope"), [yunetive29](/profile/yunetive29 "Candidate Master yunetive29"), developer: [dope](/profile/dope "Master dope"), [yunetive29](/profile/yunetive29 "Candidate Master yunetive29") 475 476 [1946F - Nobody is needed](/contest/1946/problem/F "Codeforces Round 936 (Div. 2)") 477 478 **Editorial** 479 480 Tutorial is loading... 481 482 **Solution** 483 484 ``` 485 #include <bits/stdc++.h> 486 487 using i64 = long long; 488 489 template<class Info> 490 struct Fenwick { 491 std::vector<Info> t; 492 int n; 493 494 Fenwick(int n = 0) : n(n) { 495 t.resize(n); 496 } 497 498 void add(int x, const Info &v) { 499 for (int i = x + 1; i <= n; i += i & -i) { 500 t[i - 1] = t[i - 1] + v; 501 } 502 } 503 504 Info sum(int x) { 505 x++; 506 Info res = Info(); 507 for (int i = x; i > 0; i -= i & -i) { 508 res = res + t[i - 1]; 509 } 510 return res; 511 } 512 513 Info rangeSum(int l, int r) { 514 Info res = sum(r) - sum(l - 1); 515 return res; 516 } 517 }; 518 519 void solve() { 520 int n, q; 521 std::cin >> n >> q; 522 std::vector<int> a(n), pos(n + 1); 523 for (int i = 0; i < n; i++) { 524 std::cin >> a[i]; 525 } 526 std::reverse(a.begin(), a.end()); 527 for (int i = 0; i < n; i++) { 528 pos[a[i]] = i; 529 } 530 constexpr int K = 19; 531 std::vector<i64> res(q); 532 std::vector<std::vector<std::pair<int, int>>> qry(n); 533 for (int i = 0; i < q; i++) { 534 int l, r; 535 std::cin >> l >> r; 536 l--, r--; 537 std::swap(l, r); 538 l = n - l - 1; 539 r = n - r - 1; 540 qry[r].emplace_back(l, i); 541 } 542 std::vector<i64> dp(n + 1); 543 Fenwick<i64> f(n); 544 for (int r = 0; r < n; r++) { 545 int x = a[r]; 546 dp[x] = 1; 547 // n * log(n) * log(n) 548 for (int y = x; y <= n; y += x) { 549 if (pos[y] > pos[x]) { 550 continue; 551 } 552 for (int z = 2 * y; z <= n; z += y) { 553 if (pos[z] > pos[y]) { 554 continue; 555 } 556 dp[z] += dp[y]; 557 } 558 } 559 // n * log(n) * log(n) 560 for (int y = x; y <= n; y += x) { 561 f.add(pos[y], dp[y]); 562 dp[y] = 0; 563 } 564 // q * log(n) 565 for (auto [l, i] : qry[r]) { 566 res[i] += f.rangeSum(l, r); 567 } 568 } 569 for (int i = 0; i < q; i++) { 570 std::cout << res[i] << " \n"[i == q - 1]; 571 } 572 } 573 574 signed main() { 575 std::ios::sync_with_stdio(false); 576 std::cin.tie(nullptr); 577 578 int t = 1; 579 std::cin >> t; 580 581 while (t--) { 582 solve(); 583 } 584 } 585 ```