2026.md (10588B)
1 Source: https://codeforces.com/blog/entry/135680 2 3 [2026A - Perpendicular Segments](/contest/2026/problem/A "Educational Codeforces Round 171 (Rated for Div. 2)") 4 5 Idea: [adedalic](/profile/adedalic "International Master adedalic") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 int main() { 18 int t; cin >> t; 19 while (t--) { 20 int X, Y, K; 21 cin >> X >> Y >> K; 22 int M = min(X, Y); 23 cout << "0 0 " << M << " " << M << endl; 24 cout << "0 " << M << " " << M << " 0" << endl; 25 } 26 } 27 ``` 28 29 [2026B - Black Cells](/contest/2026/problem/B "Educational Codeforces Round 171 (Rated for Div. 2)") 30 31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 32 33 **Tutorial** 34 35 Tutorial is loading... 36 37 **Solution (Neon)** 38 39 ``` 40 #include <bits/stdc++.h> 41 42 using namespace std; 43 44 int main() { 45 int t; 46 cin >> t; 47 while (t--) { 48 int n; 49 cin >> n; 50 vector<long long> a(n); 51 for (auto& x : a) cin >> x; 52 53 long long ans = 1e18; 54 55 auto upd = [&](vector<long long> a) { 56 sort(a.begin(), a.end()); 57 for (int i = 1; i < (int)a.size(); ++i) 58 if (a[i - 1] == a[i]) return; 59 long long res = 0; 60 for (int i = 0; i < (int)a.size(); i += 2) 61 res = max(res, a[i + 1] - a[i]); 62 ans = min(ans, res); 63 }; 64 65 if (n % 2 == 0) { 66 upd(a); 67 cout << ans << '\n'; 68 continue; 69 } 70 71 for (int i = 0; i < n; ++i) { 72 for (int x : {-1, 1}) { 73 a.push_back(a[i] + x); 74 upd(a); 75 a.pop_back(); 76 } 77 } 78 79 cout << ans << '\n'; 80 } 81 } 82 ``` 83 84 [2026C - Action Figures](/contest/2026/problem/C "Educational Codeforces Round 171 (Rated for Div. 2)") 85 86 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution (BledDest)** 93 94 ``` 95 #include<bits/stdc++.h> 96 97 using namespace std; 98 99 const int N = 400043; 100 char buf[N]; 101 102 bool can(const string& s, int k) 103 { 104 int n = s.size(); 105 vector<int> used(n); 106 for(int i = n - 1; i >= 0; i--) 107 if(k > 0 && s[i] == '1') 108 { 109 used[i] = 1; 110 k--; 111 } 112 int cur = 0; 113 for(int i = 0; i < n; i++) 114 if(used[i]) 115 { 116 cur--; 117 if(cur < 0) return false; 118 } 119 else cur++; 120 return true; 121 } 122 123 void solve() 124 { 125 int n; 126 scanf("%d", &n); 127 scanf("%s", buf); 128 if(n == 1) 129 { 130 puts("1"); 131 return; 132 } 133 string s = buf; 134 int count_1 = 0; 135 for(auto x : s) if (x == '1') count_1++; 136 int l = 1; 137 int r = count_1 + 1; 138 while(r - l > 1) 139 { 140 int mid = (l + r) / 2; 141 if(can(s, mid)) 142 l = mid; 143 else 144 r = mid; 145 } 146 long long ans = 0; 147 for(int i = n - 1; i >= 0; i--) 148 if(s[i] == '1' && l > 0) 149 l--; 150 else 151 ans += (i + 1); 152 printf("%lld\n", ans); 153 } 154 155 int main() 156 { 157 int t; 158 scanf("%d", &t); 159 for(int i = 0; i < t; i++) 160 solve(); 161 } 162 ``` 163 164 [2026D - Sums of Segments](/contest/2026/problem/D "Educational Codeforces Round 171 (Rated for Div. 2)") 165 166 Idea: [shnirelman](/profile/shnirelman "International Grandmaster shnirelman") 167 168 **Tutorial** 169 170 Tutorial is loading... 171 172 **Solution (BledDest)** 173 174 ``` 175 #include<bits/stdc++.h> 176 177 using namespace std; 178 179 const int MOD = 998244353; 180 181 int n; 182 183 vector<long long> a; 184 vector<long long> pa; 185 vector<long long> ppa; 186 vector<long long> start; 187 vector<long long> block; 188 vector<long long> pblock; 189 190 vector<long long> prefix_sums(vector<long long> v) 191 { 192 int k = v.size(); 193 vector<long long> res(k + 1); 194 for(int i = 0; i < k; i++) res[i + 1] = res[i] + v[i]; 195 return res; 196 } 197 198 long long get_partial(int l, int r1, int r2) 199 { 200 // s(l, r1) + s(l, r1 + 1) + ... + s(l, r2 - 1) 201 if(r2 <= r1) return 0ll; 202 int cnt = r2 - r1; 203 long long rem = pa[l] * cnt; 204 long long add = ppa[r2 + 1] - ppa[r1 + 1]; 205 return add - rem; 206 } 207 208 pair<int, int> convert(long long i) 209 { 210 int idx = upper_bound(start.begin(), start.end(), i) - start.begin() - 1; 211 pair<int, int> res = {idx, i - start[idx] + idx}; 212 return res; 213 } 214 215 long long query(long long l, long long r) 216 { 217 pair<int, int> lf = convert(l); 218 pair<int, int> rg = convert(r); 219 long long res = pblock[rg.first + 1] - pblock[lf.first]; 220 if(lf.second != lf.first) res -= get_partial(lf.first, lf.first, lf.second); 221 if(rg.second != n - 1) res -= get_partial(rg.first, rg.second + 1, n); 222 return res; 223 } 224 225 int main() 226 { 227 scanf("%d", &n); 228 a.resize(n); 229 for(int i = 0; i < n; i++) scanf("%lld", &a[i]); 230 pa = prefix_sums(a); 231 ppa = prefix_sums(pa); 232 start = {0}; 233 for(int i = n; i >= 1; i--) 234 start.push_back(start.back() + i); 235 block.resize(n); 236 for(int i = 0; i < n; i++) 237 block[i] = get_partial(i, i, n); 238 pblock = prefix_sums(block); 239 int q; 240 scanf("%d", &q); 241 for(int i = 0; i < q; i++) 242 { 243 long long l, r; 244 scanf("%lld %lld", &l, &r); 245 printf("%lld\n", query(l - 1, r - 1)); 246 } 247 248 } 249 ``` 250 251 [2026E - Best Subsequence](/contest/2026/problem/E "Educational Codeforces Round 171 (Rated for Div. 2)") 252 253 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 254 255 **Tutorial** 256 257 Tutorial is loading... 258 259 **Solution (Neon)** 260 261 ``` 262 #include <bits/stdc++.h> 263 264 using namespace std; 265 266 #define sz(a) int((a).size()) 267 268 template<typename T = int> 269 struct Dinic { 270 struct edge { 271 int u, rev; 272 T cap, flow; 273 }; 274 275 int n, s, t; 276 T flow; 277 vector<int> lst; 278 vector<int> d; 279 vector<vector<edge>> g; 280 281 Dinic() {} 282 283 Dinic(int n, int s, int t) : n(n), s(s), t(t) { 284 g.resize(n); 285 d.resize(n); 286 lst.resize(n); 287 flow = 0; 288 } 289 290 void add_edge(int v, int u, T cap, bool directed = true) { 291 g[v].push_back({u, sz(g[u]), cap, 0}); 292 g[u].push_back({v, sz(g[v]) - 1, directed ? 0 : cap, 0}); 293 } 294 295 T dfs(int v, T flow) { 296 if (v == t) return flow; 297 if (flow == 0) return 0; 298 T result = 0; 299 for (; lst[v] < sz(g[v]); ++lst[v]) { 300 edge& e = g[v][lst[v]]; 301 if (d[e.u] != d[v] + 1) continue; 302 T add = dfs(e.u, min(flow, e.cap - e.flow)); 303 if (add > 0) { 304 result += add; 305 flow -= add; 306 e.flow += add; 307 g[e.u][e.rev].flow -= add; 308 } 309 if (flow == 0) break; 310 } 311 return result; 312 } 313 314 bool bfs() { 315 fill(d.begin(), d.end(), -1); 316 queue<int> q({s}); 317 d[s] = 0; 318 while (!q.empty() && d[t] == -1) { 319 int v = q.front(); q.pop(); 320 for (auto& e : g[v]) { 321 if (d[e.u] == -1 && e.cap - e.flow > 0) { 322 q.push(e.u); 323 d[e.u] = d[v] + 1; 324 } 325 } 326 } 327 return d[t] != -1; 328 } 329 330 T calc() { 331 T add; 332 while (bfs()) { 333 fill(lst.begin(), lst.end(), 0); 334 while((add = dfs(s, numeric_limits<T>::max())) > 0) 335 flow += add; 336 } 337 return flow; 338 } 339 }; 340 341 const int B = 60; 342 const int INF = 1e9; 343 344 int main() { 345 int t; 346 cin >> t; 347 while (t--) { 348 int n; 349 cin >> n; 350 int s = n + B, t = n + B + 1; 351 Dinic mf(t + 1, s, t); 352 for (int i = 0; i < n; ++i) { 353 long long x; 354 cin >> x; 355 mf.add_edge(s, i, 1); 356 for (int j = 0; j < B; ++j) { 357 if ((x >> j) & 1) mf.add_edge(i, j + n, INF); 358 } 359 } 360 for (int i = 0; i < B; ++i) mf.add_edge(i + n, t, 1); 361 cout << n - mf.calc() << '\n'; 362 } 363 } 364 ``` 365 366 [2026F - Bermart Ice Cream](/contest/2026/problem/F "Educational Codeforces Round 171 (Rated for Div. 2)") 367 368 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 369 370 **Tutorial** 371 372 Tutorial is loading... 373 374 **Solution (awoo)** 375 376 ``` 377 #include <bits/stdc++.h> 378 379 #define forn(i, n) for (int i = 0; i < int(n); i++) 380 381 using namespace std; 382 383 const int P = 2000 + 5; 384 385 struct item{ 386 int p, t; 387 }; 388 389 struct minstack { 390 stack<item> st; 391 stack<array<int, P>> dp; 392 int get(int p) {return dp.empty() ? 0 : dp.top()[p];} 393 bool empty() {return st.empty();} 394 int size() {return st.size();} 395 void push(item it) { 396 if (empty()){ 397 dp.push({}); 398 for (int i = 0; i < P; ++i) 399 dp.top()[i] = 0; 400 } 401 else{ 402 dp.push(dp.top()); 403 } 404 st.push(it); 405 for (int i = P - it.p - 1; i >= 0; --i) 406 dp.top()[i + it.p] = max(dp.top()[i + it.p], dp.top()[i] + it.t); 407 } 408 void pop() { 409 st.pop(); 410 dp.pop(); 411 } 412 item top() { 413 return st.top(); 414 } 415 void swap(minstack &x) { 416 st.swap(x.st); 417 dp.swap(x.dp); 418 } 419 }; 420 421 struct mindeque { 422 minstack l, r, t; 423 void rebalance() { 424 bool f = false; 425 if (r.empty()) {f = true; l.swap(r);} 426 int sz = r.size() / 2; 427 while (sz--) {t.push(r.top()); r.pop();} 428 while (!r.empty()) {l.push(r.top()); r.pop();} 429 while (!t.empty()) {r.push(t.top()); t.pop();} 430 if (f) l.swap(r); 431 } 432 int get(int p) { 433 int ans = 0; 434 for (int i = 0; i <= p; ++i) 435 ans = max(ans, l.get(i) + r.get(p - i)); 436 return ans; 437 } 438 bool empty() {return l.empty() && r.empty();} 439 int size() {return l.size() + r.size();} 440 void push_front(item it) {l.push(it);} 441 void push_back(item it) {r.push(it);} 442 void pop_front() {if (l.empty()) rebalance(); l.pop();} 443 void pop_back() {if (r.empty()) rebalance(); r.pop();} 444 item front() {if (l.empty()) rebalance(); return l.top();} 445 item back() {if (r.empty()) rebalance(); return r.top();} 446 void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);} 447 }; 448 449 struct edge{ 450 int u, tp, p, t; 451 }; 452 453 struct query{ 454 int i, p; 455 }; 456 457 vector<vector<edge>> g; 458 vector<vector<query>> qs; 459 vector<int> ans; 460 mindeque ks; 461 462 void dfs(int v){ 463 for (auto& [i, p] : qs[v]){ 464 ans[i] = ks.get(p); 465 } 466 for (auto& [u, tp, p, t] : g[v]){ 467 if (tp == 0){ 468 dfs(u); 469 } 470 else if (tp == -1){ 471 auto it = ks.front(); 472 ks.pop_front(); 473 dfs(u); 474 ks.push_front({it.p, it.t}); 475 } 476 else{ 477 ks.push_back({p, t}); 478 dfs(u); 479 ks.pop_back(); 480 } 481 } 482 } 483 484 int main() { 485 cin.tie(0); 486 ios::sync_with_stdio(false); 487 int q; 488 cin >> q; 489 vector<int> st(1); 490 vector<int> where(q, -1); 491 int cnt = 1, cnt_real = 1; 492 where[0] = 0; 493 g.push_back({}); 494 qs.push_back({}); 495 496 auto copy_shop = [&](int x, bool real){ 497 g.push_back({}); 498 qs.push_back({}); 499 st.push_back(st[x]); 500 if (real){ 501 where[cnt_real] = cnt; 502 ++cnt_real; 503 } 504 ++cnt; 505 }; 506 507 forn(i, q){ 508 int tp, x; 509 cin >> tp >> x; 510 --x; 511 int v = where[x], u = -1; 512 if (tp != 4){ 513 copy_shop(v, tp == 1); 514 u = cnt - 1; 515 } 516 if (tp == 1){ 517 g[v].push_back({u, 0, -1, -1}); 518 continue; 519 } 520 if (tp == 3){ 521 g[v].push_back({u, -1, -1, -1}); 522 ++st[u]; 523 where[x] = u; 524 continue; 525 } 526 int p; 527 cin >> p; 528 if (tp == 4){ 529 qs[v].push_back({i, p}); 530 continue; 531 } 532 int t; 533 cin >> t; 534 g[v].push_back({u, 1, p, t}); 535 where[x] = u; 536 } 537 538 ans.assign(q, -1); 539 dfs(0); 540 forn(i, q) if (ans[i] != -1) cout << ans[i] << '\n'; 541 return 0; 542 } 543 ```