1140.md (9923B)
1 Source: https://codeforces.com/blog/entry/66147 2 3 [1140A - Detective Book](/contest/1140/problem/A "Educational Codeforces Round 62 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (adedalic)** 10 11 ``` 12 #include<bits/stdc++.h> 13 using namespace std; 14 15 int n; 16 vector<int> a; 17 18 inline bool read() { 19 if(!(cin >> n)) 20 return false; 21 a.resize(n); 22 for(int i = 0; i < n; i++) { 23 cin >> a[i]; 24 a[i]--; 25 } 26 return true; 27 } 28 29 inline void solve() { 30 int cnt = 0, pos = 0; 31 while(pos < n) { 32 cnt++; 33 int mx = pos; 34 while(pos < n && pos <= mx) { 35 mx = max(mx, a[pos]); 36 pos++; 37 } 38 } 39 cout << cnt << endl; 40 } 41 42 int main() { 43 #ifdef _DEBUG 44 freopen("input.txt", "r", stdin); 45 #endif 46 if(read()) { 47 solve(); 48 } 49 return 0; 50 } 51 ``` 52 53 [1140B - Good String](/contest/1140/problem/B "Educational Codeforces Round 62 (Rated for Div. 2)") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (Roms)** 60 61 ``` 62 #include <bits/stdc++.h> 63 64 using namespace std; 65 66 int t, n; 67 string s; 68 69 int main(){ 70 cin >> t; 71 for(int tc = 0; tc < t; ++tc){ 72 cin >> n >> s; 73 int res = n - 1; 74 for(int i = 0; i < n; ++i) 75 if(s[i] == '>' || s[n - 1 - i] == '<') 76 res = min(res, i); 77 78 cout << res << endl; 79 } 80 81 return 0; 82 } 83 ``` 84 85 [1140C - Playlist](/contest/1140/problem/C "Educational Codeforces Round 62 (Rated for Div. 2)") 86 87 **Tutorial** 88 89 Tutorial is loading... 90 91 **Solution (Roms)** 92 93 ``` 94 #include <bits/stdc++.h> 95 96 using namespace std; 97 98 const int N = 300009; 99 100 int n, k; 101 pair<int, int> a[N]; 102 103 int main() { 104 cin >> n >> k; 105 106 for(int i = 0; i < n; ++i) 107 cin >> a[i].second >> a[i].first; 108 109 sort(a, a + n); 110 long long res = 0; 111 long long sum = 0; 112 set<pair<int, int> > s; 113 for(int i = n - 1; i >= 0; --i){ 114 s.insert(make_pair(a[i].second, i)); 115 sum += a[i].second; 116 while(s.size() > k){ 117 auto it = s.begin(); 118 sum -= it->first; 119 s.erase(it); 120 } 121 122 res = max(res, sum * a[i].first); 123 } 124 125 cout << res << endl; 126 return 0; 127 } 128 ``` 129 130 [1140D - Minimum Triangulation](/contest/1140/problem/D "Educational Codeforces Round 62 (Rated for Div. 2)") 131 132 **Tutorial** 133 134 Tutorial is loading... 135 136 **Solution (adedalic)** 137 138 ``` 139 #include<bits/stdc++.h> 140 using namespace std; 141 142 int main() { 143 int n; cin >> n; 144 145 long long ans = 0; 146 for(int id = 2; id < n; id++) 147 ans += 1ll * id * (id + 1); 148 149 cout << ans << endl; 150 } 151 ``` 152 153 [1140E - Palindrome-less Arrays](/contest/1140/problem/E "Educational Codeforces Round 62 (Rated for Div. 2)") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution (adedalic)** 160 161 ``` 162 #include<bits/stdc++.h> 163 164 using namespace std; 165 166 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 167 #define sz(a) int((a).size()) 168 169 #define x first 170 #define y second 171 172 typedef long long li; 173 typedef pair<int, int> pt; 174 175 const int MOD = 998244353; 176 int norm(int a) { 177 while(a >= MOD) a -= MOD; 178 while(a < 0) a += MOD; 179 return a; 180 } 181 int mul(int a, int b) { 182 return int(a * 1ll * b % MOD); 183 } 184 185 int n, k; 186 vector<int> a; 187 188 inline bool read() { 189 if(!(cin >> n >> k)) 190 return false; 191 a.resize(n); 192 fore(i, 0, n) 193 cin >> a[i]; 194 return true; 195 } 196 197 pair<int, int> calc(int len) { 198 if(len == 0) return {0, 1}; 199 if(len & 1) { 200 auto res = calc(len >> 1); 201 return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))), 202 norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))}; 203 } 204 auto res = calc(len - 1); 205 return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))}; 206 } 207 208 vector<int> curArray; 209 210 int calcSeg(int l, int r) { 211 if(r >= sz(curArray)) { 212 int len = r - l - 1, cf = 1; 213 if(l < 0) 214 len--, cf = k; 215 if(len == 0) return cf; 216 217 auto res = calc(len - 1); 218 return mul(cf, norm(res.x + mul(k - 1, res.y))); 219 } 220 if(l < 0) { 221 if(r - l == 1) return 1; 222 auto res = calc(r - l - 2); 223 return norm(res.x + mul(k - 1, res.y)); 224 } 225 auto res = calc(r - l - 1); 226 return curArray[l] == curArray[r] ? res.x : res.y; 227 } 228 229 inline void solve() { 230 int ans = 1; 231 fore(k, 0, 2) { 232 curArray.clear(); 233 for(int i = 0; 2 * i + k < n; i++) 234 curArray.push_back(a[2 * i + k]); 235 236 int lst = -1; 237 fore(i, 0, sz(curArray)){ 238 if(curArray[i] == -1) continue; 239 ans = mul(ans, calcSeg(lst, i)); 240 lst = i; 241 } 242 ans = mul(ans, calcSeg(lst, sz(curArray))); 243 } 244 cout << ans << endl; 245 } 246 247 int main() { 248 #ifdef _DEBUG 249 freopen("input.txt", "r", stdin); 250 int tt = clock(); 251 #endif 252 ios_base::sync_with_stdio(0); 253 cin.tie(0), cout.tie(0); 254 cout << fixed << setprecision(15); 255 256 if(read()) { 257 solve(); 258 259 #ifdef _DEBUG 260 cerr << "TIME = " << clock() - tt << endl; 261 tt = clock(); 262 #endif 263 } 264 return 0; 265 } 266 ``` 267 268 [1140F - Extending Set of Points](/contest/1140/problem/F "Educational Codeforces Round 62 (Rated for Div. 2)") 269 270 **Tutorial** 271 272 Tutorial is loading... 273 274 **Solution (BledDest)** 275 276 ``` 277 #include <bits/stdc++.h> 278 279 using namespace std; 280 281 typedef long long li; 282 283 #define x first 284 #define y second 285 286 const int N = 300043; 287 const int K = 300000; 288 289 int p[2 * N]; 290 int s1[2 * N]; 291 int s2[2 * N]; 292 li ans = 0; 293 294 int* where[80 * N]; 295 int val[80 * N]; 296 int cur = 0; 297 298 void change(int& x, int y) 299 { 300 where[cur] = &x; 301 val[cur] = x; 302 x = y; 303 cur++; 304 } 305 306 void rollback() 307 { 308 cur--; 309 (*where[cur]) = val[cur]; 310 } 311 312 int get(int x) 313 { 314 if(p[x] == x) 315 return x; 316 return get(p[x]); 317 } 318 319 void merge(int x, int y) 320 { 321 x = get(x); 322 y = get(y); 323 if(x == y) return; 324 ans -= s1[x] * 1ll * s2[x]; 325 ans -= s1[y] * 1ll * s2[y]; 326 if(s1[x] + s2[x] < s1[y] + s2[y]) 327 swap(x, y); 328 change(p[y], x); 329 change(s1[x], s1[x] + s1[y]); 330 change(s2[x], s2[x] + s2[y]); 331 ans += s1[x] * 1ll * s2[x]; 332 } 333 334 void init() 335 { 336 for(int i = 0; i < K; i++) 337 { 338 p[i] = i; 339 p[i + K] = i + K; 340 s1[i] = 1; 341 s2[i + K] = 1; 342 } 343 } 344 345 vector<pair<int, int> > T[4 * N]; 346 347 void add(int v, int l, int r, int L, int R, pair<int, int> val) 348 { 349 if(L >= R) return; 350 if(L == l && R == r) 351 T[v].push_back(val); 352 else 353 { 354 int m = (l + r) / 2; 355 add(v * 2 + 1, l, m, L, min(R, m), val); 356 add(v * 2 + 2, m, r, max(m, L), R, val); 357 } 358 } 359 360 li res[N]; 361 362 void dfs(int v, int l, int r) 363 { 364 li last_ans = ans; 365 int state = cur; 366 for(auto x : T[v]) 367 merge(x.x, x.y + K); 368 if(l == r - 1) 369 res[l] = ans; 370 else 371 { 372 int m = (l + r) / 2; 373 dfs(v * 2 + 1, l, m); 374 dfs(v * 2 + 2, m, r); 375 } 376 while(cur != state) rollback(); 377 ans = last_ans; 378 } 379 380 int main() 381 { 382 int q; 383 scanf("%d", &q); 384 map<pair<int, int>, int> last; 385 for(int i = 0; i < q; i++) 386 { 387 int x, y; 388 scanf("%d %d", &x, &y); 389 --x; 390 --y; 391 pair<int, int> p = make_pair(x, y); 392 if(last.count(p)) 393 { 394 add(0, 0, q, last[p], i, p); 395 last.erase(p); 396 } 397 else 398 last[p] = i; 399 } 400 for(auto x : last) 401 add(0, 0, q, x.y, q, x.x); 402 init(); 403 dfs(0, 0, q); 404 for(int i = 0; i < q; i++) 405 printf("%I64d ", res[i]); 406 } 407 ``` 408 409 [1140G - Double Tree](/contest/1140/problem/G "Educational Codeforces Round 62 (Rated for Div. 2)") 410 411 **Tutorial** 412 413 Tutorial is loading... 414 415 **Solution (BledDest)** 416 417 ``` 418 #include <bits/stdc++.h> 419 420 using namespace std; 421 422 typedef long long li; 423 424 #define x first 425 #define y second 426 427 const int N = 600043; 428 429 li d1[N]; 430 li d2[N][2]; 431 li dist_temp[N][2]; 432 vector<pair<int, int> > g[N]; 433 vector<int> qs[N]; 434 int qq[N][2]; 435 li ans[N]; 436 int n; 437 int used[N]; 438 int cnt[N]; 439 int last[N]; 440 int cc = 1; 441 442 void preprocess() 443 { 444 set<pair<li, int> > q; 445 for(int i = 0; i < n; i++) 446 q.insert(make_pair(d1[i], i)); 447 while(!q.empty()) 448 { 449 int k = q.begin()->second; 450 q.erase(q.begin()); 451 for(auto e : g[k]) 452 { 453 int to = e.first; 454 li w = d2[e.second][0] + d2[e.second][1]; 455 if(d1[to] > w + d1[k]) 456 { 457 q.erase(make_pair(d1[to], to)); 458 d1[to] = w + d1[k]; 459 q.insert(make_pair(d1[to], to)); 460 } 461 } 462 } 463 } 464 465 void dfs1(int x, int p = -1) 466 { 467 if(used[x]) return; 468 cnt[x] = 1; 469 for(auto y : g[x]) 470 { 471 int to = y.first; 472 if(!used[to] && to != p) 473 { 474 dfs1(to, x); 475 cnt[x] += cnt[to]; 476 } 477 } 478 } 479 480 vector<int> cur_queries; 481 pair<int, int> c; 482 int S = 0; 483 484 void find_centroid(int x, int p = -1) 485 { 486 if(used[x]) return; 487 int mx = 0; 488 for(auto y : g[x]) 489 { 490 int to = y.first; 491 if(!used[to] && to != p) 492 { 493 find_centroid(to, x); 494 mx = max(mx, cnt[to]); 495 } 496 } 497 if(p != -1) 498 mx = max(mx, S - cnt[x]); 499 c = min(c, make_pair(mx, x)); 500 } 501 502 void dfs2(int x, int p = -1, int e = -1) 503 { 504 if(used[x]) return; 505 if(p == -1) 506 { 507 dist_temp[x * 2][0] = dist_temp[x * 2 + 1][1] = 0ll; 508 dist_temp[x * 2][1] = dist_temp[x * 2 + 1][0] = d1[x]; 509 } 510 else 511 { 512 for(int k = 0; k < 2; k++) 513 { 514 li& D0 = dist_temp[x * 2][k]; 515 li& D1 = dist_temp[x * 2 + 1][k]; 516 D0 = dist_temp[p * 2][k] + d2[e][0]; 517 D1 = dist_temp[p * 2 + 1][k] + d2[e][1]; 518 D0 = min(D0, D1 + d1[x]); 519 D1 = min(D1, D0 + d1[x]); 520 } 521 } 522 for(auto y : qs[x]) 523 { 524 if(ans[y] != -1) continue; 525 if(last[y] == cc) 526 cur_queries.push_back(y); 527 else 528 last[y] = cc; 529 } 530 for(auto y : g[x]) 531 { 532 int to = y.first; 533 if(!used[to] && to != p) 534 dfs2(to, x, y.second); 535 } 536 } 537 538 void centroid(int v) 539 { 540 if(used[v]) return; 541 dfs1(v); 542 S = cnt[v]; 543 c = make_pair(int(1e9), -1); 544 find_centroid(v); 545 int C = c.second; 546 used[C] = 1; 547 for(auto y : g[C]) 548 centroid(y.first); 549 cc++; 550 cur_queries.clear(); 551 used[C] = 0; 552 dfs2(C); 553 for(auto x : cur_queries) 554 { 555 int u = qq[x][0]; 556 int v = qq[x][1]; 557 ans[x] = min(dist_temp[u][0] + dist_temp[v][0], dist_temp[u][1] + dist_temp[v][1]); 558 } 559 } 560 561 int main() 562 { 563 scanf("%d", &n); 564 for(int i = 0; i < n; i++) 565 scanf("%I64d", &d1[i]); 566 for(int i = 0; i < n - 1; i++) 567 { 568 int x, y; 569 li w1, w2; 570 scanf("%d %d %I64d %I64d", &x, &y, &w1, &w2); 571 --x; 572 --y; 573 d2[i][0] = w1; 574 d2[i][1] = w2; 575 g[x].push_back(make_pair(y, i)); 576 g[y].push_back(make_pair(x, i)); 577 } 578 int q; 579 scanf("%d", &q); 580 for(int i = 0; i < q; i++) 581 { 582 scanf("%d", &qq[i][0]); 583 scanf("%d", &qq[i][1]); 584 --qq[i][0]; 585 --qq[i][1]; 586 qs[qq[i][0] / 2].push_back(i); 587 qs[qq[i][1] / 2].push_back(i); 588 } 589 preprocess(); 590 for(int i = 0; i < q; i++) 591 ans[i] = -1; 592 centroid(0); 593 for(int i = 0; i < q; i++) 594 cout << ans[i] << endl; 595 } 596 ```