1418.md (11260B)
1 Source: https://codeforces.com/blog/entry/82673 2 3 [1418A - Buying Torches](/contest/1418/problem/A "Educational Codeforces Round 95 (Rated for Div. 2)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (vovuh)** 12 13 ``` 14 for i in range(int(input())): 15 x, y, k = map(int, input().split()) 16 print(((y + 1) * k - 1 + x - 2) // (x - 1) + k) 17 ``` 18 19 [1418B - Negative Prefixes](/contest/1418/problem/B "Educational Codeforces Round 95 (Rated for Div. 2)") 20 21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Ne0n25)** 28 29 ``` 30 #include <bits/stdc++.h> 31 32 using namespace std; 33 34 #define sz(a) int((a).size()) 35 #define forn(i, n) for (int i = 0; i < int(n); ++i) 36 37 void solve() { 38 int n; 39 cin >> n; 40 vector<int> a(n), b(n), c; 41 forn(i, n) cin >> a[i]; 42 forn(i, n) cin >> b[i]; 43 forn(i, n) if (!b[i]) 44 c.push_back(a[i]); 45 sort(c.rbegin(), c.rend()); 46 int j = 0; 47 forn(i, n) { 48 if (b[i]) cout << a[i] << ' '; 49 else cout << c[j++] << ' '; 50 } 51 cout << '\n'; 52 } 53 54 int main() { 55 int T; 56 cin >> T; 57 while (T--) solve(); 58 } 59 ``` 60 61 [1418C - Mortal Kombat Tower](/contest/1418/problem/C "Educational Codeforces Round 95 (Rated for Div. 2)") 62 63 Idea: [vovuh](/profile/vovuh "Master vovuh") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution (vovuh)** 70 71 ``` 72 #include <bits/stdc++.h> 73 74 using namespace std; 75 76 int main() { 77 #ifdef _DEBUG 78 freopen("input.txt", "r", stdin); 79 // freopen("output.txt", "w", stdout); 80 #endif 81 82 int t; 83 cin >> t; 84 while (t--) { 85 int n; 86 cin >> n; 87 vector<int> a(n); 88 for (auto &it : a) cin >> it; 89 int ans = 0; 90 ans += a[0] == 1; 91 for (int i = 1; i < n; ++i) { 92 if (a[i] == 0) { 93 continue; 94 } 95 int j = i; 96 while (j < n && a[j] == 1) { 97 ++j; 98 } 99 ans += (j - i) / 3; 100 i = j - 1; 101 } 102 cout << ans << endl; 103 } 104 105 return 0; 106 } 107 ``` 108 109 [1418D - Trash Problem](/contest/1418/problem/D "Educational Codeforces Round 95 (Rated for Div. 2)") 110 111 Idea: [vovuh](/profile/vovuh "Master vovuh") 112 113 **Tutorial** 114 115 Tutorial is loading... 116 117 **Solution (vovuh)** 118 119 ``` 120 #include <bits/stdc++.h> 121 122 using namespace std; 123 124 int get(const set<int> &x, const multiset<int> &len) { 125 if (len.empty()) return 0; 126 return *x.rbegin() - *x.begin() - *len.rbegin(); 127 } 128 129 void add(int p, set<int> &x, multiset<int> &len) { 130 x.insert(p); 131 auto it = x.find(p); 132 int prv = -1, nxt = -1; 133 if (it != x.begin()) { 134 --it; 135 len.insert(p - *it); 136 prv = *it; 137 ++it; 138 } 139 ++it; 140 if (it != x.end()) { 141 len.insert(*it - p); 142 nxt = *it; 143 } 144 if (prv != -1 && nxt != -1) { 145 len.erase(len.find(nxt - prv)); 146 } 147 } 148 149 void rem(int p, set<int> &x, multiset<int> &len) { 150 auto it = x.find(p); 151 int prv = -1, nxt = -1; 152 if (it != x.begin()) { 153 --it; 154 len.erase(len.find(p - *it)); 155 prv = *it; 156 ++it; 157 } 158 ++it; 159 if (it != x.end()) { 160 len.erase(len.find(*it - p)); 161 nxt = *it; 162 } 163 x.erase(p); 164 if (prv != -1 && nxt != -1) { 165 len.insert(nxt - prv); 166 } 167 } 168 169 int main() { 170 #ifdef _DEBUG 171 freopen("input.txt", "r", stdin); 172 // freopen("output.txt", "w", stdout); 173 #endif 174 175 int n, q; 176 cin >> n >> q; 177 set<int> x; 178 multiset<int> len; 179 for (int i = 0; i < n; ++i) { 180 int p; 181 cin >> p; 182 add(p, x, len); 183 } 184 185 cout << get(x, len) << endl; 186 for (int i = 0; i < q; ++i) { 187 int t, p; 188 cin >> t >> p; 189 if (t == 0) { 190 rem(p, x, len); 191 } else { 192 add(p, x, len); 193 } 194 cout << get(x, len) << endl; 195 } 196 197 return 0; 198 } 199 ``` 200 201 [1418E - Expected Damage](/contest/1418/problem/E "Educational Codeforces Round 95 (Rated for Div. 2)") 202 203 Idea: [Roms](/profile/Roms "Master Roms") 204 205 **Tutorial** 206 207 Tutorial is loading... 208 209 **Solution (Roms)** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 using namespace std; 215 216 const int N = int(2e5) + 9; 217 const int MOD = 998244353; 218 219 int mul(int a, int b) { 220 return (a * 1LL * b) % MOD; 221 } 222 223 int bp(int a, int n) { 224 int res = 1; 225 for (; n > 0; n /= 2) { 226 if (n & 1) res = mul(res, a); 227 a = mul(a, a); 228 } 229 230 return res; 231 } 232 233 int inv(int a) { 234 int ia = bp(a, MOD - 2); 235 assert(mul(a, ia) == 1); 236 return ia; 237 } 238 239 int n, m; 240 int d[N]; 241 long long sd[N]; 242 243 long long sum (int l, int r) { 244 return (sd[r] - sd[l]) % MOD; 245 } 246 247 int main(){ 248 cin >> n >> m; 249 for (int i = 0; i < n; ++i) 250 scanf("%d", d + i); 251 sort(d, d + n); 252 for (int i = 0; i < n; ++i) 253 sd[i + 1] = sd[i] + d[i]; 254 255 for (int i = 0; i < m; ++i) { 256 int a, b; 257 scanf("%d%d", &a, &b); // dur, def 258 int cnt = (d + n) - lower_bound(d, d + n, b); 259 int res = 0; 260 if (cnt >= a) { 261 res = mul( mul(cnt - a, inv(cnt)), sum(n - cnt, n) ); 262 res += mul( mul(cnt - a + 1, inv(cnt + 1)), sum(0, n - cnt) ); 263 res %= MOD; 264 } 265 printf("%d\n", res); 266 } 267 268 return 0; 269 } 270 ``` 271 272 [1418F - Equal Product](/contest/1418/problem/F "Educational Codeforces Round 95 (Rated for Div. 2)") 273 274 Idea: [adedalic](/profile/adedalic "International Master adedalic") 275 276 **Tutorial** 277 278 Tutorial is loading... 279 280 **Solution (adedalic)** 281 282 ``` 283 #include<bits/stdc++.h> 284 285 using namespace std; 286 287 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 288 #define sz(a) int((a).size()) 289 290 #define x first 291 #define y second 292 293 typedef long long li; 294 typedef pair<int, int> pt; 295 296 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 297 return out << "(" << p.x << ", " << p.y << ")"; 298 } 299 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 300 out << "["; 301 fore(i, 0, sz(v)) { 302 if(i) out << ", "; 303 out << v[i]; 304 } 305 return out << "]"; 306 } 307 308 const int INF = int(1e9); 309 const li INF64 = li(1e18); 310 311 int n, m; 312 li l, r; 313 314 inline bool read() { 315 if(!(cin >> n >> m)) 316 return false; 317 cin >> l >> r; 318 return true; 319 } 320 321 const int N = int(2e5) + 555; 322 vector<int> divs[N]; 323 324 inline void solve() { 325 fore(d, 1, N) { 326 for(int pos = d; pos < N; pos += d) 327 divs[pos].push_back(d); 328 } 329 330 li lf = m + 1, rg = m; 331 vector<int> cnt(m + 1, 0); 332 vector<int> id(m + 1, -1); 333 set<int> curDivs; 334 335 vector< vector<int> > ans(n + 1); 336 337 fore(x1, 1, n + 1) { 338 li newlf = (l + x1 - 1) / x1; 339 li newrg = r / x1; 340 assert(newrg - newlf + 1 >= 0); 341 342 while (lf > newlf) { 343 lf--; 344 for (int d : divs[lf]) { 345 if (cnt[d] == 0) 346 curDivs.insert(d); 347 cnt[d]++; 348 id[d] = (int)lf; 349 } 350 } 351 while (rg > newrg) { 352 for (int d : divs[rg]) { 353 cnt[d]--; 354 if (cnt[d] == 0) 355 curDivs.erase(d); 356 } 357 rg--; 358 } 359 360 for (int a : divs[x1]) { 361 auto it = curDivs.upper_bound(a); 362 if (it == curDivs.end()) 363 continue; 364 365 int b = *it; 366 if (x1 / a * 1ll * b <= n) { 367 int y1 = id[b]; 368 369 ans[x1] = {x1, y1, x1 / a * b, y1 / b * a}; 370 } 371 } 372 } 373 374 fore(i, 1, n + 1) { 375 if (ans[i].empty()) 376 cout << -1 << '\n'; 377 else { 378 cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << " " << ans[i][3] << '\n'; 379 } 380 } 381 } 382 383 int main() { 384 #ifdef _DEBUG 385 freopen("input.txt", "r", stdin); 386 int tt = clock(); 387 #endif 388 ios_base::sync_with_stdio(false); 389 cin.tie(0), cout.tie(0); 390 cout << fixed << setprecision(15); 391 392 if(read()) { 393 solve(); 394 395 #ifdef _DEBUG 396 cerr << "TIME = " << clock() - tt << endl; 397 tt = clock(); 398 #endif 399 } 400 return 0; 401 } 402 ``` 403 404 [1418G - Three Occurrences](/contest/1418/problem/G "Educational Codeforces Round 95 (Rated for Div. 2)") 405 406 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [Roms](/profile/Roms "Master Roms") 407 408 **Tutorial** 409 410 Tutorial is loading... 411 412 **Solution 1 (pikmike)** 413 414 ``` 415 #include <bits/stdc++.h> 416 417 using namespace std; 418 419 #define forn(i, n) for(int i = 0; i < int(n); i++) 420 421 const int N = 60; 422 423 typedef array<int, N> num; 424 425 num operator ^(const num &a, const num &b){ 426 num c; 427 forn(i, N){ 428 c[i] = a[i] + b[i]; 429 if (c[i] >= 3) c[i] -= 3; 430 } 431 return c; 432 } 433 434 mt19937 rnd(42); 435 436 int main(){ 437 int n; 438 scanf("%d", &n); 439 vector<int> a(n); 440 forn(i, n){ 441 scanf("%d", &a[i]); 442 --a[i]; 443 } 444 445 vector<num> nums(n); 446 forn(i, n) forn(j, N) nums[i][j] = rnd() % 3; 447 448 vector<vector<int>> pos(n); 449 vector<num> pr(1); 450 map<num, int> cnt; 451 cnt[pr[0]] = 1; 452 int cur = 0; 453 long long ans = 0; 454 forn(i, n){ 455 pr.push_back(pr.back() ^ nums[a[i]]); 456 pos[a[i]].push_back(i); 457 if (pos[a[i]].size() >= 4){ 458 while (cur <= pos[a[i]][int(pos[a[i]].size()) - 4]){ 459 --cnt[pr[cur]]; 460 ++cur; 461 } 462 } 463 ans += cnt[pr.back()]; 464 ++cnt[pr.back()]; 465 } 466 467 printf("%lld\n", ans); 468 } 469 ``` 470 471 **Solution 2 (pikmike)** 472 473 ``` 474 #include <bits/stdc++.h> 475 476 using namespace std; 477 478 #define forn(i, n) for(int i = 0; i < int(n); i++) 479 480 typedef unsigned long long uli; 481 482 vector<int> a; 483 vector<pair<int, int>> t; 484 vector<int> ps; 485 486 pair<int, int> merge(const pair<int, int> &a, const pair<int, int> &b){ 487 if (a.first != b.first) 488 return min(a, b); 489 return make_pair(a.first, a.second + b.second); 490 } 491 492 void push(int v){ 493 if (v * 2 + 1 < int(ps.size())){ 494 ps[v * 2] += ps[v]; 495 ps[v * 2 + 1] += ps[v]; 496 } 497 t[v].first += ps[v]; 498 ps[v] = 0; 499 } 500 501 void build(int v, int l, int r){ 502 if (l == r - 1){ 503 t[v] = make_pair(0, 1); 504 return; 505 } 506 int m = (l + r) / 2; 507 build(v * 2, l, m); 508 build(v * 2 + 1, m, r); 509 t[v] = merge(t[v * 2], t[v * 2 + 1]); 510 } 511 512 void upd(int v, int l, int r, int L, int R, int val){ 513 push(v); 514 if (L >= R) 515 return; 516 if (l == L && r == R){ 517 ps[v] = val; 518 push(v); 519 return; 520 } 521 int m = (l + r) / 2; 522 upd(v * 2, l, m, L, min(m, R), val); 523 upd(v * 2 + 1, m, r, max(m, L), R, val); 524 t[v] = merge(t[v * 2], t[v * 2 + 1]); 525 } 526 527 int main(){ 528 int n; 529 scanf("%d", &n); 530 a.resize(n); 531 forn(i, n){ 532 scanf("%d", &a[i]); 533 --a[i]; 534 } 535 t.resize(4 * n); 536 ps.resize(4 * n); 537 build(1, 0, n); 538 vector<vector<int>> pos(n, vector<int>(1, -1)); 539 long long ans = 0; 540 forn(i, n){ 541 int k = pos[a[i]].size(); 542 if (k >= 1) upd(1, 0, n, pos[a[i]][k - 1] + 1, i + 1, 1); 543 if (k >= 3) upd(1, 0, n, pos[a[i]][k - 3] + 1, pos[a[i]][k - 2] + 1, -1); 544 if (k >= 4) upd(1, 0, n, pos[a[i]][k - 4] + 1, pos[a[i]][k - 3] + 1, 1); 545 pos[a[i]].push_back(i); 546 push(1); 547 if (t[1].first == 0) ans += t[1].second - (n - i - 1); 548 } 549 printf("%lld\n", ans); 550 } 551 ```