1982.md (9566B)
1 Source: https://codeforces.com/blog/entry/130839 2 3 Thank you for participating! I hope you enjoyed the tasks. 4 5 One of the testers ([redpanda](/profile/redpanda "Expert redpanda")) did a wonderful [video analysis](https://youtu.be/-btzjr-u4dM) tasks A-C, I highly recommend watching it. 6 7 [1982A - Soccer](/contest/1982/problem/A "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution (74TrAkToR)** 14 15 ``` 16 t = int(input()) 17 for T in range(t): 18 la, lb = map(int, input().split()) 19 ra, rb = map(int, input().split()) 20 if la > lb: 21 la, lb, ra, rb = lb, la, rb, ra 22 if la < lb and rb < ra: 23 print("NO") 24 else: 25 print("YES") 26 ``` 27 28 [1982B - Collatz Conjecture](/contest/1982/problem/B "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (FelixArg)** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 void solve(){ 42 long long x, y, k; 43 cin >> x >> y >> k; 44 while (k > 0 && x != 1) { 45 long long ost = (x / y + 1) * y - x; 46 ost = max(1ll, ost); 47 ost = min(ost, k); 48 x += ost; 49 while (x % y == 0) { 50 x /= y; 51 } 52 k -= ost; 53 } 54 cout << x + k % (y - 1) << '\n'; 55 } 56 57 int main() 58 { 59 #ifdef FELIX 60 auto _clock_start = chrono::high_resolution_clock::now(); 61 #endif 62 ios_base::sync_with_stdio(false); 63 cin.tie(0); 64 cout.tie(0); 65 66 int tests = 1; 67 cin >> tests; 68 for (int test = 0; test < tests; test++){ 69 solve(); 70 } 71 72 #ifdef FELIX 73 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 74 chrono::high_resolution_clock::now() 75 - _clock_start).count() << "ms." << endl; 76 #endif 77 return 0; 78 } 79 ``` 80 81 [1982C - Boring Day](/contest/1982/problem/C "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 82 83 **Hint 1** 84 85 All the numbers $a_{i}$ are positive, can it help somehow? 86 87 **Hint 2** 88 89 Try using dynamic programming. 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution 1 (FelixArg)** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 const int inf = 1000000007; 103 104 void solve(){ 105 int n, l, r; 106 cin >> n >> l >> r; 107 vector<int> a(n); 108 for (int i = 0; i < n; i++){ 109 cin >> a[i]; 110 } 111 112 vector<long long> pref(n + 1); 113 for (int i = 0; i < n; i++){ 114 pref[i + 1] = pref[i] + a[i]; 115 } 116 117 vector<int> dp(n + 1); 118 int s = 0; 119 int j = -1; 120 for (int i = 0; i < n; i++){ 121 dp[i + 1] = max(dp[i + 1], dp[i]); 122 if (j < i){ 123 j = i; 124 s = 0; 125 } 126 while(j < n && s < l){ 127 s += a[j++]; 128 } 129 if (s >= l && s <= r){ 130 dp[j] = max(dp[j], dp[i] + 1); 131 } 132 s -= a[i]; 133 } 134 135 cout << dp[n] << '\n'; 136 } 137 138 int main() 139 { 140 #ifdef FELIX 141 auto _clock_start = chrono::high_resolution_clock::now(); 142 #endif 143 ios_base::sync_with_stdio(false); 144 cin.tie(0); 145 cout.tie(0); 146 int tests = 1; 147 cin >> tests; 148 for (int test = 0; test < tests; test++){ 149 solve(); 150 } 151 #ifdef FELIX 152 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 153 chrono::high_resolution_clock::now() 154 - _clock_start).count() << "ms." << endl; 155 #endif 156 return 0; 157 } 158 ``` 159 160 **Solution 2 (74TrAkToR)** 161 162 ``` 163 t = int(input()) 164 for T in range(t): 165 n, l, r = map(int, input().split()) 166 a = [int(x) for x in input().split()] 167 ans = 0 168 cur = 0 169 L, R = 0, 0 170 while L < n: 171 while R < n and cur < l: 172 cur += a[R] 173 R += 1 174 if l <= cur and cur <= r: 175 ans += 1 176 L = R 177 cur = 0 178 else: 179 cur -= a[L] 180 L += 1 181 print(ans) 182 ``` 183 184 [1982D - Beauty of the mountains](/contest/1982/problem/D "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 185 186 **Hint 1** 187 188 How does the difference between heights change if we choose a specific submatrix? 189 190 **Hint 2** 191 192 It is worth reducing the problem to a mathematical construction. Maybe something from number theory can help? 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution (FelixArg)** 199 200 ``` 201 import math 202 203 def solve(): 204 n, m, k = map(int, input().split()) 205 a = [[int(x) for x in input().split()] for j in range(n)] 206 s = [input() for i in range(n)] 207 pref = [[0 for i in range(m + 1)] for j in range(n + 1)] 208 diff = 0 209 for i in range(n): 210 cur = 0 211 for j in range(m): 212 if s[i][j] == '1': 213 cur += 1 214 diff += a[i][j] 215 else: 216 diff -= a[i][j] 217 pref[i + 1][j + 1] = pref[i][j + 1] + cur 218 if diff == 0: 219 print("YES") 220 return 221 g = 0 222 for i in range(n - k + 1): 223 for j in range(m - k + 1): 224 f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j] 225 f = abs(k * k - 2 * f) 226 g = math.gcd(g, f) 227 if g == 0 or diff % g != 0: 228 print("NO") 229 else: 230 print("YES") 231 232 233 if __name__ == "__main__": 234 t = int(input()) 235 for _ in range(t): 236 solve() 237 ``` 238 239 [1982E - Number of k-good subarrays](/contest/1982/problem/E "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 240 241 **Hint** 242 243 Try using the divide-and-conquer approach. 244 245 **Tutorial** 246 247 Tutorial is loading... 248 249 **Solution (FelixArg)** 250 251 ``` 252 #include <bits/stdc++.h> 253 254 using namespace std; 255 256 const int MOD = 1000000007; 257 258 map<pair<long long, int>, tuple<int, long long, long long>> mem; 259 260 tuple<int, long long, long long> calc(long long n, int k){ 261 if (k < 0){ 262 return tuple{0, 0ll, 0ll}; 263 } 264 if (n == 1){ 265 return tuple{1, 1ll, 1ll}; 266 } 267 int bit = 63 - __builtin_clzll(n); 268 long long mid = (1ll << bit); 269 if (mid == n){ 270 mid >>= 1; 271 if (mem.count({n, k})){ 272 return mem[{n, k}]; 273 } 274 } 275 auto [f1, s1, e1] = calc(mid, k); 276 auto [f2, s2, e2] = calc(n - mid, k - 1); 277 278 int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD; 279 f1 = (f1 * 1ll - sub1 + MOD) % MOD; 280 int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD; 281 f2 = (f2 * 1ll - sub2 + MOD) % MOD; 282 283 long long p = (e1 + s2) % MOD; 284 int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD; 285 long long s_cur = s1; 286 long long e_cur = e2; 287 if (s1 == e1 && s1 != 0){ 288 s_cur = (s1 + s2); 289 } 290 if (s2 == e2 && s2 != 0){ 291 e_cur = (e1 + e2); 292 } 293 if ((mid << 1) == n){ 294 mem[{n, k}] = tuple{f_cur, s_cur, e_cur}; 295 } 296 return tuple{f_cur, s_cur, e_cur}; 297 }; 298 299 void solve(){ 300 long long n; 301 int k; 302 cin >> n >> k; 303 cout << get<0>(calc(n, k)) << '\n'; 304 } 305 306 int main() 307 { 308 #ifdef FELIX 309 auto _clock_start = chrono::high_resolution_clock::now(); 310 #endif 311 ios_base::sync_with_stdio(false); 312 cin.tie(0); 313 cout.tie(0); 314 315 int tests = 1; 316 cin >> tests; 317 for (int test = 0; test < tests; test++){ 318 solve(); 319 } 320 321 #ifdef FELIX 322 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 323 chrono::high_resolution_clock::now() 324 - _clock_start).count() << "ms." << endl; 325 #endif 326 return 0; 327 } 328 ``` 329 330 [1982F - Sorting Problem Again](/contest/1982/problem/F "Codeforces Round 955 (Div. 2, with prizes from NEAR!)") 331 332 **Hint** 333 334 If you maintain a set of such indexes $i$ that $a_{i} \lt a_{i - 1}$, then can this help in any way? 335 336 **Tutorial** 337 338 Tutorial is loading... 339 340 **Solution (FelixArg)** 341 342 ``` 343 #include <bits/stdc++.h> 344 345 using namespace std; 346 347 const int inf = 1000000007; 348 349 struct SegTree{ 350 vector<int> mn, mx; 351 int n; 352 SegTree(int _n): n(_n){ 353 mx.assign(2 * n, -inf); 354 mn.resize(2 * n, inf); 355 } 356 357 void upd(int pos, int val){ 358 mx[pos + n] = val; 359 mn[pos + n] = val; 360 pos = (pos + n) >> 1; 361 for (;pos > 0; pos >>= 1){ 362 mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]); 363 mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]); 364 } 365 } 366 367 pair<int,int> get(int l, int r){ 368 pair<int,int> res = {-inf, inf}; 369 l += n; 370 r += n + 1; 371 for (;l < r; l >>= 1, r >>= 1){ 372 if (l & 1) { 373 res.first = max(res.first, mx[l]); 374 res.second = min(res.second, mn[l++]); 375 } 376 if (r & 1) { 377 res.first = max(res.first, mx[--r]); 378 res.second = min(res.second, mn[r]); 379 } 380 } 381 return res; 382 } 383 }; 384 385 void solve(){ 386 int n; 387 cin >> n; 388 vector<int> a(n); 389 for (int i = 0; i < n; i++){ 390 cin >> a[i]; 391 } 392 393 SegTree tree(n); 394 set<int> st; 395 for (int i = 0; i < n; i++){ 396 tree.upd(i, a[i]); 397 if (i > 0 && a[i] < a[i - 1]){ 398 st.insert(i); 399 } 400 } 401 402 function<int(int, int)> find_pref = [&](int pos, int x){ 403 if (pos < 0){ 404 return 0; 405 } 406 int l = 0, r = pos; 407 while(l <= r){ 408 int m = l + (r - l) / 2; 409 if (a[m] > x){ 410 r = m - 1; 411 } 412 else{ 413 l = m + 1; 414 } 415 } 416 return r + 1; 417 }; 418 419 function<int(int, int)> find_suff = [&](int pos, int x){ 420 if (pos >= n){ 421 return n - 1; 422 } 423 int l = pos, r = n - 1; 424 while(l <= r){ 425 int m = l + (r - l) / 2; 426 if (a[m] >= x){ 427 r = m - 1; 428 } 429 else{ 430 l = m + 1; 431 } 432 } 433 return r; 434 }; 435 436 function<void()> query = [&](){ 437 if (st.empty()){ 438 cout << -1 << ' ' << -1 << '\n'; 439 return; 440 } 441 int l = *st.begin() - 1; 442 int r = *(--st.end()); 443 444 auto [mx, mn] = tree.get(l, r); 445 446 cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n'; 447 }; 448 449 query(); 450 int q; 451 cin >> q; 452 for (int i = 0; i < q; i++){ 453 int pos, val; 454 cin >> pos >> val; 455 pos--; 456 if (pos > 0 && a[pos] < a[pos - 1]){ 457 st.erase(pos); 458 } 459 if (pos + 1 < n && a[pos + 1] < a[pos]){ 460 st.erase(pos + 1); 461 } 462 a[pos] = val; 463 tree.upd(pos, val); 464 if (pos > 0 && a[pos] < a[pos - 1]){ 465 st.insert(pos); 466 } 467 if (pos + 1 < n && a[pos + 1] < a[pos]){ 468 st.insert(pos + 1); 469 } 470 query(); 471 } 472 } 473 474 int main() 475 { 476 #ifdef FELIX 477 auto _clock_start = chrono::high_resolution_clock::now(); 478 #endif 479 ios_base::sync_with_stdio(false); 480 cin.tie(0); 481 cout.tie(0); 482 int tests = 1; 483 cin >> tests; 484 for (int test = 0; test < tests; test++){ 485 solve(); 486 } 487 #ifdef FELIX 488 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 489 chrono::high_resolution_clock::now() 490 - _clock_start).count() << "ms." << endl; 491 #endif 492 return 0; 493 } 494 ```