1175.md (12390B)
1 Source: https://codeforces.com/blog/entry/67484 2 3 [1175A - From Hero to Zero](/contest/1175/problem/A "Educational Codeforces Round 66 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Roms)** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 long long n, k; 19 20 int main(){ 21 int tc; 22 cin >> tc; 23 for(int i = 0; i < tc; ++i){ 24 cin >> n >> k; 25 long long res = 0; 26 while(n > 0){ 27 if(n % k == 0){ 28 n /= k; 29 ++res; 30 } 31 else{ 32 long long rem = n % k; 33 res += rem; 34 n -= rem; 35 } 36 } 37 38 cout << res << endl; 39 } 40 return 0; 41 } 42 ``` 43 44 [1175B - Catch Overflow!](/contest/1175/problem/B "Educational Codeforces Round 66 (Rated for Div. 2)") 45 46 Idea: [awoo](/profile/awoo "Master awoo") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution (PikMike)** 53 54 ``` 55 #include <bits/stdc++.h> 56 57 #define forn(i, n) for(int i = 0; i < int(n); i++) 58 59 using namespace std; 60 61 const long long INF = 1ll << 32; 62 63 int main(){ 64 int l; 65 cin >> l; 66 67 stack<long long> cur; 68 cur.push(1); 69 70 long long res = 0; 71 forn(_, l){ 72 string t; 73 cin >> t; 74 if (t == "for"){ 75 int x; 76 cin >> x; 77 cur.push(min(INF, cur.top() * x)); 78 } 79 else if (t == "end"){ 80 cur.pop(); 81 } 82 else{ 83 res += cur.top(); 84 } 85 } 86 87 if (res >= INF) 88 cout << "OVERFLOW!!!" << endl; 89 else 90 cout << res << endl; 91 } 92 ``` 93 94 [1175C - Electrification](/contest/1175/problem/C "Educational Codeforces Round 66 (Rated for Div. 2)") 95 96 Idea: [adedalic](/profile/adedalic "International Master adedalic") 97 98 **Tutorial** 99 100 Tutorial is loading... 101 102 **Solution (adedalic)** 103 104 ``` 105 #include<bits/stdc++.h> 106 107 using namespace std; 108 109 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 110 #define sz(a) int((a).size()) 111 112 int n, k; 113 vector<int> a; 114 115 inline bool read() { 116 if(!(cin >> n >> k)) 117 return false; 118 a.resize(n); 119 fore(i, 0, n) 120 cin >> a[i]; 121 return true; 122 } 123 124 inline void solve() { 125 pair<int, int> ans = {int(1e9) + 7, -1}; 126 fore(i, 0, n - k) { 127 int dist = a[i + k] - a[i]; 128 ans = min(ans, make_pair(dist, a[i] + dist / 2)); 129 } 130 131 cout << ans.second << endl; 132 } 133 134 int main() { 135 #ifdef _DEBUG 136 freopen("input.txt", "r", stdin); 137 int tt = clock(); 138 #endif 139 ios_base::sync_with_stdio(false); 140 cin.tie(0), cout.tie(0); 141 cout << fixed << setprecision(15); 142 143 int tc; cin >> tc; 144 145 while(tc--) { 146 read(); 147 solve(); 148 149 #ifdef _DEBUG 150 cerr << "TIME = " << clock() - tt << endl; 151 tt = clock(); 152 #endif 153 } 154 return 0; 155 } 156 ``` 157 158 [1175D - Array Splitting](/contest/1175/problem/D "Educational Codeforces Round 66 (Rated for Div. 2)") 159 160 Idea: [adedalic](/profile/adedalic "International Master adedalic") 161 162 **Tutorial** 163 164 Tutorial is loading... 165 166 **Solution (Roms)** 167 168 ``` 169 #include<bits/stdc++.h> 170 171 using namespace std; 172 173 const int N = 300009; 174 175 int n, k; 176 int a[N]; 177 178 int main(){ 179 cin >> n >> k; 180 for(int i = 0; i < n; ++i) 181 cin >> a[i]; 182 183 long long sum = 0; 184 vector <long long> v; 185 for(int i = n - 1; i >= 0; --i){ 186 sum += a[i]; 187 if(i > 0) v.push_back(sum); 188 } 189 190 long long res = sum; 191 192 sort(v.begin(), v.end()); 193 reverse(v.begin(), v.end()); 194 195 196 for(int i = 0; i < k - 1; ++i) 197 res += v[i]; 198 199 cout << res << endl; 200 return 0; 201 } 202 ``` 203 204 [1175E - Minimal Segment Cover](/contest/1175/problem/E "Educational Codeforces Round 66 (Rated for Div. 2)") 205 206 Idea: [adedalic](/profile/adedalic "International Master adedalic") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution 1 (PikMike)** 213 214 ``` 215 #include <bits/stdc++.h> 216 217 using namespace std; 218 219 #define x first 220 #define y second 221 #define forn(i, n) for(int i = 0; i < int(n); i++) 222 223 const int N = 500 * 1000 + 13; 224 const int LOGN = 18; 225 226 int n, m; 227 pair<int, int> a[N], q[N]; 228 229 int nxt[N]; 230 int up[LOGN][N]; 231 232 int main(){ 233 scanf("%d%d", &n, &m); 234 forn(i, n) 235 scanf("%d%d", &a[i].x, &a[i].y); 236 forn(i, m) 237 scanf("%d%d", &q[i].x, &q[i].y); 238 239 sort(a, a + n); 240 241 int lst = 0; 242 pair<int, int> mx(0, -1); 243 forn(i, N){ 244 while (lst < n && a[lst].x == i){ 245 mx = max(mx, make_pair(a[lst].y, lst)); 246 ++lst; 247 } 248 nxt[i] = (mx.x <= i ? -1 : mx.y); 249 } 250 251 forn(i, n) 252 up[0][i] = nxt[a[i].y]; 253 for (int j = 1; j < LOGN; ++j) forn(i, n){ 254 if (up[j - 1][i] == -1) 255 up[j][i] = -1; 256 else 257 up[j][i] = up[j - 1][up[j - 1][i]]; 258 } 259 260 forn(i, m){ 261 int x = nxt[q[i].x]; 262 263 if (x == -1){ 264 puts("-1"); 265 continue; 266 } 267 268 int res = 1; 269 for (int j = LOGN - 1; j >= 0; --j){ 270 int y = up[j][x]; 271 if (y == -1) 272 continue; 273 if (a[y].y < q[i].y){ 274 res += (1 << j); 275 x = y; 276 } 277 } 278 279 if (a[x].y >= q[i].y) 280 printf("%d\n", res); 281 else if (up[0][x] == -1) 282 puts("-1"); 283 else 284 printf("%d\n", res + 1); 285 } 286 } 287 ``` 288 289 **Solution 2 (PikMike)** 290 291 ``` 292 #include <bits/stdc++.h> 293 294 using namespace std; 295 296 #define x first 297 #define y second 298 #define forn(i, n) for(int i = 0; i < int(n); i++) 299 300 const int N = 500 * 1000 + 13; 301 302 int n, m; 303 pair<int, int> a[N], q[N]; 304 305 int nxt[N]; 306 int ans[N]; 307 308 pair<int, int> p[N]; 309 310 pair<int, int> get(int x, int r){ 311 if (x == -1) 312 return make_pair(-1, -1); 313 if (a[x].y >= r) 314 return make_pair(x, 0); 315 auto res = get(p[x].x, r); 316 if (res.x == -1) 317 p[x] = make_pair(-1, -1); 318 else 319 p[x] = make_pair(res.x, p[x].y + res.y); 320 return p[x]; 321 } 322 323 int main(){ 324 scanf("%d%d", &n, &m); 325 forn(i, n) 326 scanf("%d%d", &a[i].x, &a[i].y); 327 forn(i, m) 328 scanf("%d%d", &q[i].x, &q[i].y); 329 sort(a, a + n); 330 331 int lst = 0; 332 pair<int, int> mx(0, -1); 333 forn(i, N){ 334 while (lst < n && a[lst].x == i){ 335 mx = max(mx, make_pair(a[lst].y, lst)); 336 ++lst; 337 } 338 nxt[i] = (mx.x <= i ? -1 : mx.y); 339 } 340 341 vector<int> perm(m); 342 iota(perm.begin(), perm.end(), 0); 343 sort(perm.begin(), perm.end(), [](int a, int b){ 344 return q[a].y < q[b].y; 345 }); 346 347 forn(i, n) 348 p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1); 349 350 for (auto i : perm){ 351 int x = nxt[q[i].x]; 352 auto res = get(x, q[i].y).y; 353 ans[i] = (res == -1 ? -1 : res + 1); 354 } 355 356 forn(i, m) 357 printf("%d\n", ans[i]); 358 } 359 ``` 360 361 [1175F - The Number of Subpermutations](/contest/1175/problem/F "Educational Codeforces Round 66 (Rated for Div. 2)") 362 363 Idea: [Roms](/profile/Roms "Master Roms") 364 365 **Tutorial** 366 367 Tutorial is loading... 368 369 **Solution (Roms)** 370 371 ``` 372 #include <bits/stdc++.h> 373 374 using namespace std; 375 376 typedef pair<long long, long long> pt; 377 378 const int N = int(3e5) + 99; 379 const pt zero = make_pair(0, 0); 380 381 int n; 382 int a[N]; 383 pt hsh[N], sumHsh[N]; 384 385 void upd(pt &a, pt b){ 386 a.first ^= b.first; 387 a.second ^= b.second; 388 } 389 390 int calc(int pos){ 391 set <int> sl, sr; 392 set<pt> s; 393 int r = pos + 1, l = pos - 1; 394 pt curr = hsh[0], curl = zero; 395 s.insert(zero); 396 sr.insert(0), sl.insert(0); 397 398 int res = 0; 399 while(r < n && !sr.count(a[r])){ 400 sr.insert(a[r]); 401 upd(curr, hsh[a[r]]); 402 ++r; 403 404 while(l >= 0 && !sl.count(a[l]) && a[l] < *sr.rbegin()){ 405 sl.insert(a[l]); 406 upd(curl, hsh[a[l]]); 407 s.insert(curl); 408 --l; 409 } 410 411 pt need = sumHsh[*sr.rbegin()]; 412 upd(need, curr); 413 if(s.count(need)) ++res; 414 } 415 416 return res; 417 } 418 419 int main() { 420 long long x = 0; 421 cin >> n; 422 for(int i = 0; i < n; ++i){ 423 cin >> a[i]; 424 --a[i]; 425 x ^= a[i]; 426 } 427 428 429 mt19937_64 rnd(time(NULL)); 430 for(int i = 0; i < N; ++i){ 431 hsh[i].first = rnd() ^ x; 432 hsh[i].second = rnd() ^ x; 433 sumHsh[i] = hsh[i]; 434 if(i > 0) upd(sumHsh[i], sumHsh[i - 1]); 435 } 436 437 int res = 0; 438 439 for(int tc = 0; tc < 2; ++tc){ 440 for(int i = 0; i < n; ++i) 441 if(a[i] == 0) 442 res += calc(i) + (tc == 0); 443 reverse(a, a + n); 444 } 445 cout << res << endl; 446 447 return 0; 448 } 449 ``` 450 451 [1175G - Yet Another Partiton Problem](/contest/1175/problem/G "Educational Codeforces Round 66 (Rated for Div. 2)") 452 453 Idea: [adedalic](/profile/adedalic "International Master adedalic") 454 455 **Tutorial** 456 457 Tutorial is loading... 458 459 **Solution (adedalic)** 460 461 ``` 462 #include<bits/stdc++.h> 463 464 using namespace std; 465 466 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 467 #define sz(a) (int)((a).size()) 468 469 #define x first 470 #define y second 471 472 typedef long long li; 473 typedef pair<li, li> pt; 474 475 const int INF = int(1e9); 476 const li INF64 = li(1e9); 477 478 pt operator -(const pt &a, const pt &b) { 479 return {a.x - b.x, a.y - b.y}; 480 } 481 li operator *(const pt &a, const pt &b) { 482 return a.x * b.x + a.y * b.y; 483 } 484 li operator %(const pt &a, const pt &b) { 485 return a.x * b.y - a.y * b.x; 486 } 487 pt rotate(const pt &p) { 488 return {-p.y, p.x}; 489 } 490 491 struct LinearHull { 492 deque<pt> pts, vecs; 493 494 void addRight(const pt &l) { 495 while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) { 496 vecs.pop_back(); 497 pts.pop_back(); 498 } 499 if(!pts.empty()) 500 vecs.push_back(rotate(l - pts.back())); 501 pts.push_back(l); 502 } 503 void addLeft(const pt &l) { 504 while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) { 505 vecs.pop_front(); 506 pts.pop_front(); 507 } 508 if(!pts.empty()) 509 vecs.push_front(rotate(pts.front() - l)); 510 pts.push_front(l); 511 } 512 513 li getMin(const pt &x) { 514 auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) { 515 return a % b > 0; 516 }); 517 return x * pts[it - vecs.begin()]; 518 } 519 }; 520 521 typedef unique_ptr<LinearHull> pHull; 522 523 void mergeHulls(pHull &a, pHull &b) { 524 if(sz(b->pts) >= sz(a->pts)) { 525 for(auto &p : a->pts) 526 b->addRight(p); 527 } else { 528 for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++) 529 a->addLeft(*it); 530 swap(a, b); 531 } 532 } 533 534 const int M = 1000 * 1000 + 555; 535 int szn = 0; 536 struct node { 537 pt line; 538 node *l, *r; 539 540 node() : line(), l(nullptr), r(nullptr) {} 541 node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {} 542 } nodes[M]; 543 544 typedef node* tree; 545 546 tree getNode(const pt &line, tree l, tree r) { 547 assert(szn < M); 548 nodes[szn] = node(line, l, r); 549 return &nodes[szn++]; 550 } 551 tree copy(tree v) { 552 if(v == nullptr) return v; 553 return getNode(v->line, v->l, v->r); 554 } 555 556 li f(const pt &line, int x) { 557 return line * pt{x, 1}; 558 } 559 560 tree addLine(tree v, int l, int r, pt line) { 561 if(!v) 562 return getNode(line, nullptr, nullptr); 563 int mid = (l + r) >> 1; 564 bool lf = f(line, l) < f(v->line, l); 565 bool md = f(line, mid) < f(v->line, mid); 566 567 if(md) 568 swap(v->line, line); 569 570 if(l + 1 == r) 571 return v; 572 else if(lf != md) 573 v->l = addLine(copy(v->l), l, mid, line); 574 else 575 v->r = addLine(copy(v->r), mid, r, line); 576 return v; 577 } 578 579 li getMin(tree v, int l, int r, int x) { 580 if(!v) return INF64; 581 if(l + 1 == r) 582 return f(v->line, x); 583 int mid = (l + r) >> 1; 584 585 if(x < mid) 586 return min(f(v->line, x), getMin(v->l, l, mid, x)); 587 else 588 return min(f(v->line, x), getMin(v->r, mid, r, x)); 589 } 590 591 int n, k; 592 vector<li> a; 593 594 inline bool read() { 595 if(!(cin >> n >> k)) 596 return false; 597 a.resize(n); 598 599 fore(i, 0, n) 600 cin >> a[i]; 601 return true; 602 } 603 604 struct state { 605 int pos; 606 pHull hull; 607 tree v; 608 609 state() : pos(-1), hull(nullptr), v(nullptr) {} 610 }; 611 612 vector<li> d[2]; 613 614 inline void solve() { 615 int maxn = (int)*max_element(a.begin(), a.end()) + 3; 616 fore(k, 0, 2) 617 d[k].resize(n + 1, INF64); 618 619 d[0][0] = 0; 620 fore(_k, 1, k + 1) { 621 szn = 0; 622 623 int ck = _k & 1; 624 int nk = ck ^ 1; 625 626 vector< state > st; 627 628 fore(i, 0, sz(d[ck])) { 629 d[ck][i] = INF64; 630 if(!st.empty()) 631 d[ck][i] = getMin(st.back().v, 0, maxn, i); 632 633 if(i >= sz(a)) 634 continue; 635 636 state curVal; 637 curVal.pos = i; 638 curVal.hull = make_unique<LinearHull>(); 639 curVal.hull->addRight({-i, d[nk][i]}); 640 curVal.v = nullptr; 641 642 while(!st.empty() && a[st.back().pos] < a[i]) { 643 mergeHulls(st.back().hull, curVal.hull); 644 st.pop_back(); 645 } 646 if(!st.empty()) 647 curVal.v = st.back().v; 648 649 li val = curVal.hull->getMin({a[i], 1}); 650 curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val}); 651 652 st.push_back(move(curVal)); 653 } 654 } 655 cout << d[k & 1][n] << endl; 656 } 657 658 int main() { 659 #ifdef _DEBUG 660 freopen("input.txt", "r", stdin); 661 int tt = clock(); 662 #endif 663 ios_base::sync_with_stdio(false); 664 cin.tie(0), cout.tie(0); 665 cout << fixed << setprecision(15); 666 667 if(read()) { 668 solve(); 669 670 #ifdef _DEBUG 671 cerr << "TIME = " << clock() - tt << endl; 672 tt = clock(); 673 #endif 674 } 675 return 0; 676 } 677 ```