1389.md (10241B)
1 Source: https://codeforces.com/blog/entry/80809 2 3 [1389A - LCM Problem](/contest/1389/problem/A "Educational Codeforces Round 92 (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 t = int(input()) 15 for i in range(t): 16 l, r = map(int, input().split()) 17 if l * 2 > r: 18 print(-1, -1) 19 else: 20 print(l, l * 2) 21 ``` 22 23 [1389B - Array Walk](/contest/1389/problem/B "Educational Codeforces Round 92 (Rated for Div. 2)") 24 25 Idea: [Roms](/profile/Roms "Master Roms") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution 1 (pikmike)** 32 33 ``` 34 for _ in range(int(input())): 35 n, k, z = map(int, input().split()) 36 a = [int(x) for x in input().split()] 37 ans = 0 38 s = 0 39 mx = 0 40 for t in range(z + 1): 41 pos = k - 2 * t 42 if pos < 0: 43 continue 44 mx = 0 45 s = 0 46 for i in range(pos + 1): 47 if i < n - 1: 48 mx = max(mx, a[i] + a[i + 1]) 49 s += a[i] 50 ans = max(ans, s + mx * t) 51 print(ans) 52 ``` 53 54 **Solution 2 (pikmike)** 55 56 ``` 57 for _ in range(int(input())): 58 n, k, z = map(int, input().split()) 59 a = [int(x) for x in input().split()] 60 ans = 0 61 s = 0 62 mx = 0 63 for i in range(k + 1): 64 if i < n - 1: 65 mx = max(mx, a[i] + a[i + 1]) 66 s += a[i] 67 if i % 2 == k % 2: 68 tmp = (k - i) // 2 69 if tmp <= z: 70 ans = max(ans, s + mx * tmp) 71 print(ans) 72 ``` 73 74 [1389C - Good String](/contest/1389/problem/C "Educational Codeforces Round 92 (Rated for Div. 2)") 75 76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution (Ne0n25)** 83 84 ``` 85 #include <bits/stdc++.h> 86 87 using namespace std; 88 89 #define sz(a) int((a).size()) 90 #define forn(i, n) for (int i = 0; i < int(n); ++i) 91 92 int solve(const string& s, int x, int y) { 93 int res = 0; 94 for (auto c : s) if (c - '0' == x) { 95 ++res; 96 swap(x, y); 97 } 98 if (x != y && res % 2 == 1) 99 --res; 100 return res; 101 } 102 103 void solve() { 104 string s; 105 cin >> s; 106 int ans = 0; 107 forn(x, 10) forn(y, 10) 108 ans = max(ans, solve(s, x, y)); 109 cout << sz(s) - ans << endl; 110 } 111 112 int main() { 113 int T; 114 cin >> T; 115 while (T--) solve(); 116 } 117 ``` 118 119 [1389D - Segment Intersections](/contest/1389/problem/D "Educational Codeforces Round 92 (Rated for Div. 2)") 120 121 Idea: [adedalic](/profile/adedalic "International Master adedalic") 122 123 **Tutorial** 124 125 Tutorial is loading... 126 127 **Solution (adedalic)** 128 129 ``` 130 import kotlin.math.* 131 132 fun main() { 133 repeat(readLine()!!.toInt()) { 134 val (n, k) = readLine()!!.split(' ').map { it.toLong() } 135 val (l1, r1) = readLine()!!.split(' ').map { it.toLong() } 136 val (l2, r2) = readLine()!!.split(' ').map { it.toLong() } 137 138 var ans = 1e18.toLong() 139 if (max(l1, l2) <= min(r1, r2)) { 140 val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2))) 141 val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2)) 142 ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2 143 } else { 144 val invest = max(l1, l2) - min(r1, r2) 145 for (cntInv in 1..n) { 146 var curAns = invest * cntInv 147 val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv 148 curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2 149 ans = min(ans, curAns) 150 } 151 } 152 println(ans) 153 } 154 } 155 ``` 156 157 [1389E - Calendar Ambiguity](/contest/1389/problem/E "Educational Codeforces Round 92 (Rated for Div. 2)") 158 159 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Solution (pikmike)** 166 167 ``` 168 fun gcd(a: Long, b: Long): Long { 169 if (a == 0L) return b 170 return gcd(b % a, a) 171 } 172 173 fun main() { 174 repeat(readLine()!!.toInt()) { 175 val (m, d, w) = readLine()!!.split(' ').map { it.toLong() } 176 val w2 = w / gcd(d - 1, w) 177 val mn = minOf(m, d) 178 var cnt = mn / w2 179 println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2) 180 } 181 } 182 ``` 183 184 [1389F - Bicolored Segments](/contest/1389/problem/F "Educational Codeforces Round 92 (Rated for Div. 2)") 185 186 Idea: [Roms](/profile/Roms "Master Roms") 187 188 **Tutorial** 189 190 Tutorial is loading... 191 192 **Solution 1 (Ne0n25)** 193 194 ``` 195 #include <bits/stdc++.h> 196 197 using namespace std; 198 199 #define x first 200 #define y second 201 #define pb push_back 202 #define mp make_pair 203 #define all(a) (a).begin(), (a).end() 204 #define forn(i, n) for (int i = 0; i < int(n); ++i) 205 206 typedef pair<int, int> pt; 207 208 const int N = 200 * 1000; 209 210 int n; 211 int l[N], r[N], t[N]; 212 set<pt> st[2]; 213 214 int main() { 215 scanf("%d", &n); 216 forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i]; 217 218 vector<pair<int, pt>> ev; 219 forn(i, n) { 220 ev.pb(mp(l[i], mp(0, i))); 221 ev.pb(mp(r[i], mp(1, i))); 222 } 223 224 sort(all(ev)); 225 226 int ans = 0; 227 for (auto it : ev) { 228 int i = it.y.y; 229 if (it.y.x) { 230 int j = t[i]; 231 int k = j ^ 1; 232 if (st[j].count(mp(r[i], i)) && !st[k].empty()) { 233 ++ans; 234 st[k].erase(st[k].begin()); 235 } 236 if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i)); 237 } else { 238 st[t[i]].insert(mp(r[i], i)); 239 } 240 } 241 242 printf("%d\n", n - ans); 243 } 244 ``` 245 246 **Solution 2 (Ne0n25)** 247 248 ``` 249 #include <bits/stdc++.h> 250 251 using namespace std; 252 253 #define x first 254 #define y second 255 #define pb push_back 256 #define mp make_pair 257 #define sz(a) int((a).size()) 258 #define all(a) (a).begin(), (a).end() 259 #define forn(i, n) for (int i = 0; i < int(n); ++i) 260 261 typedef pair<int, int> pt; 262 263 const int INF = 1e9; 264 const int N = 200 * 1000; 265 266 int n; 267 vector<pt> a[2]; 268 269 struct segtree { 270 int n; 271 vector<int> t, ps; 272 segtree(int n) : n(n) { 273 t.resize(4 * n, -INF); 274 ps.resize(4 * n, 0); 275 } 276 277 void push(int v, int l, int r) { 278 if (l + 1 != r) { 279 ps[v * 2 + 1] += ps[v]; 280 ps[v * 2 + 2] += ps[v]; 281 } 282 t[v] += ps[v]; 283 ps[v] = 0; 284 } 285 286 void upd(int v, int l, int r, int pos, int val) { 287 push(v, l, r); 288 if (l + 1 == r) { 289 t[v] = val; 290 return; 291 } 292 int m = (l + r) >> 1; 293 if (pos < m) upd(v * 2 + 1, l, m, pos, val); 294 else upd(v * 2 + 2, m, r, pos, val); 295 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 296 } 297 298 void add(int v, int l, int r, int L, int R, int val) { 299 push(v, l, r); 300 if (L >= R) return; 301 if (l == L && r == R) { 302 ps[v] += val; 303 push(v, l, r); 304 return; 305 } 306 int m = (l + r) >> 1; 307 add(v * 2 + 1, l, m, L, min(m, R), val); 308 add(v * 2 + 2, m, r, max(m, L), R, val); 309 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 310 } 311 312 int get(int v, int l, int r, int L, int R) { 313 push(v, l, r); 314 if (L >= R) return -INF; 315 if (l == L && r == R) 316 return t[v]; 317 int m = (l + r) >> 1; 318 int r1 = get(v * 2 + 1, l, m, L, min(m, R)); 319 int r2 = get(v * 2 + 2, m, r, max(m, L), R); 320 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 321 return max(r1, r2); 322 } 323 324 void upd(int pos, int val) { 325 return upd(0, 0, n, pos, val); 326 } 327 328 void add(int l, int r, int val) { 329 return add(0, 0, n, l, r, val); 330 } 331 332 int get(int l, int r) { 333 return get(0, 0, n, l, r); 334 } 335 }; 336 337 int main() { 338 scanf("%d", &n); 339 forn(i, n) { 340 int l, r, t; 341 scanf("%d%d%d", &l, &r, &t); 342 a[t - 1].pb(mp(r, l)); 343 } 344 345 forn(i, 2) sort(all(a[i]), [](pt a, pt b) { 346 if (a.x == b.x) return a.y > b.y; 347 return a.x < b.x; 348 }); 349 350 segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1); 351 t1.upd(0, 0); 352 t2.upd(0, 0); 353 354 int ans = 0; 355 for (int i = 0, j = 0; i + j < n; ) { 356 if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) { 357 int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1; 358 int cur = t2.get(0, pos) + 1; 359 ans = max(ans, cur); 360 t1.upd(i + 1, cur); 361 t2.add(0, pos, 1); 362 ++i; 363 } else { 364 int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1; 365 int cur = t1.get(0, pos) + 1; 366 ans = max(ans, cur); 367 t2.upd(j + 1, cur); 368 t1.add(0, pos, 1); 369 ++j; 370 } 371 } 372 373 printf("%d\n", ans); 374 } 375 ``` 376 377 [1389G - Directing Edges](/contest/1389/problem/G "Educational Codeforces Round 92 (Rated for Div. 2)") 378 379 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 380 381 **Tutorial** 382 383 Tutorial is loading... 384 385 **Solution (BledDest)** 386 387 ``` 388 #include<bits/stdc++.h> 389 390 using namespace std; 391 392 typedef long long li; 393 394 const int N = 300043; 395 396 bool is_bridge[N]; 397 int w[N]; 398 int c[N]; 399 int v[N]; 400 vector<pair<int, int> > g[N]; 401 402 vector<pair<int, int> > g2[N]; 403 int comp[N]; 404 li sum[N]; 405 li dp[N]; 406 int cnt[N]; 407 int fup[N]; 408 int tin[N]; 409 int T = 0; 410 li ans[N]; 411 int v1[N], v2[N]; 412 413 int n, m, k; 414 415 int dfs1(int x, int e) 416 { 417 tin[x] = T++; 418 fup[x] = tin[x]; 419 for(auto p : g[x]) 420 { 421 int y = p.first; 422 int i = p.second; 423 if(i == e) 424 continue; 425 if(tin[y] != -1) 426 fup[x] = min(fup[x], tin[y]); 427 else 428 { 429 fup[x] = min(fup[x], dfs1(y, i)); 430 if(fup[y] > tin[x]) 431 is_bridge[i] = true; 432 } 433 } 434 return fup[x]; 435 } 436 437 void dfs2(int x, int cc) 438 { 439 if(comp[x] != -1) 440 return; 441 comp[x] = cc; 442 cnt[cc] += v[x]; 443 sum[cc] += c[x]; 444 for(auto y : g[x]) 445 if(!is_bridge[y.second]) 446 dfs2(y.first, cc); 447 } 448 449 void process_edge(int x, int y, int m, int weight) 450 { 451 li add_dp = dp[y]; 452 if(cnt[y] > 0 && cnt[y] < k) 453 add_dp = max(0ll, add_dp - weight); 454 455 cnt[x] += m * cnt[y]; 456 dp[x] += m * add_dp; 457 } 458 459 void link(int x, int y, int weight) 460 { 461 process_edge(x, y, 1, weight); 462 } 463 464 void cut(int x, int y, int weight) 465 { 466 process_edge(x, y, -1, weight); 467 } 468 469 void dfs3(int x, int p) 470 { 471 dp[x] = sum[x]; 472 for(auto e : g2[x]) 473 { 474 int i = e.second; 475 int y = e.first; 476 if(y == p) 477 continue; 478 dfs3(y, x); 479 link(x, y, w[i]); 480 } 481 } 482 483 void dfs4(int x, int p) 484 { 485 ans[x] = dp[x]; 486 for(auto e : g2[x]) 487 { 488 int i = e.second; 489 int y = e.first; 490 if(y == p) 491 continue; 492 cut(x, y, w[i]); 493 link(y, x, w[i]); 494 dfs4(y, x); 495 cut(y, x, w[i]); 496 link(x, y, w[i]); 497 } 498 } 499 500 int main() 501 { 502 scanf("%d %d %d", &n, &m, &k); 503 for(int i = 0; i < k; i++) 504 { 505 int x; 506 scanf("%d", &x); 507 --x; 508 v[x] = 1; 509 } 510 for(int i = 0; i < n; i++) 511 scanf("%d", &c[i]); 512 for(int i = 0; i < m; i++) 513 scanf("%d", &w[i]); 514 for(int i = 0; i < m; i++) 515 { 516 scanf("%d %d", &v1[i], &v2[i]); 517 --v1[i]; 518 --v2[i]; 519 g[v1[i]].push_back(make_pair(v2[i], i)); 520 g[v2[i]].push_back(make_pair(v1[i], i)); 521 } 522 523 for(int i = 0; i < n; i++) 524 { 525 tin[i] = -1; 526 comp[i] = -1; 527 } 528 dfs1(0, -1); 529 int cc = 0; 530 for(int i = 0; i < n; i++) 531 if(comp[i] == -1) 532 dfs2(i, cc++); 533 for(int i = 0; i < m; i++) 534 if(is_bridge[i]) 535 { 536 g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i)); 537 g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i)); 538 } 539 dfs3(0, 0); 540 dfs4(0, 0); 541 for(int i = 0; i < n; i++) 542 printf("%lld ", ans[comp[i]]); 543 puts(""); 544 } 545 ```