2042.md (8655B)
1 Source: https://codeforces.com/blog/entry/136886 2 3 [2042A - Greedy Monocarp](/contest/2042/problem/A "Educational Codeforces Round 172 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int n, k; 23 cin >> n >> k; 24 vector<int> a(n); 25 for (auto& x : a) cin >> x; 26 sort(a.begin(), a.end(), greater<int>()); 27 int sum = 0; 28 for (auto& x : a) { 29 if (sum + x <= k) sum += x; 30 else break; 31 } 32 cout << k - sum << '\n'; 33 } 34 } 35 ``` 36 37 [2042B - Game with Colored Marbles](/contest/2042/problem/B "Educational Codeforces Round 172 (Rated for Div. 2)") 38 39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (BledDest)** 46 47 ``` 48 #include<bits/stdc++.h> 49 50 using namespace std; 51 52 int main() 53 { 54 int t; 55 scanf("%d", &t); 56 for(int _ = 0; _ < t; _++) 57 { 58 int n; 59 scanf("%d", &n); 60 vector<int> c(n); 61 for(int i = 0; i < n; i++) 62 { 63 scanf("%d", &c[i]); 64 --c[i]; 65 } 66 vector<int> cnt(n); 67 for(auto x : c) cnt[x]++; 68 int exactly1 = 0, morethan1 = 0; 69 for(auto x : cnt) 70 if (x == 1) 71 exactly1++; 72 else if(x > 1) 73 morethan1++; 74 printf("%d\n", morethan1 + (exactly1 + 1) / 2 * 2); 75 } 76 } 77 ``` 78 79 [2042C - Competitive Fishing](/contest/2042/problem/C "Educational Codeforces Round 172 (Rated for Div. 2)") 80 81 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution (Neon)** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 int main() { 95 int t; 96 cin >> t; 97 while (t--) { 98 int n, k; 99 string s; 100 cin >> n >> k >> s; 101 vector<int> vals; 102 int sum = 0; 103 for (int i = n - 1; i > 0; --i) { 104 sum += (s[i] == '1' ? 1 : -1); 105 if (sum > 0) vals.push_back(sum); 106 } 107 sort(vals.begin(), vals.end()); 108 int ans = 1; 109 while (k > 0 && !vals.empty()) { 110 k -= vals.back(); 111 vals.pop_back(); 112 ++ans; 113 } 114 cout << (k > 0 ? -1 : ans) << '\n'; 115 } 116 } 117 ``` 118 119 [2042D - Recommendations](/contest/2042/problem/D "Educational Codeforces Round 172 (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 #include<bits/stdc++.h> 131 using namespace std; 132 133 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 134 #define sz(a) int((a).size()) 135 136 struct Seg { 137 int l, r; 138 139 bool operator< (const Seg &oth) const { 140 if (l != oth.l) 141 return l < oth.l; 142 return r < oth.r; 143 }; 144 }; 145 146 void solve() { 147 int n; 148 cin >> n; 149 vector<Seg> seg(n); 150 for (int i = 0; i < n; i++) 151 cin >> seg[i].l >> seg[i].r; 152 153 vector<int> ans(n, 0); 154 for (int k = 0; k < 2; k++) { 155 vector<int> ord(n); 156 iota(ord.begin(), ord.end(), 0); 157 158 sort(ord.begin(), ord.end(), [&seg](int i, int j){ 159 if (seg[i].l != seg[j].l) 160 return seg[i].l < seg[j].l; 161 return seg[i].r > seg[j].r; 162 }); 163 164 set<int> bounds; 165 for (int i : ord) { 166 auto it = bounds.lower_bound(seg[i].r); 167 if (it != bounds.end()) 168 ans[i] += *it - seg[i].r; 169 bounds.insert(seg[i].r); 170 } 171 172 for (auto &s : seg) { 173 s.l = -s.l; 174 s.r = -s.r; 175 swap(s.l, s.r); 176 } 177 } 178 179 map<Seg, int> cnt; 180 for (auto s: seg) 181 cnt[s]++; 182 for (int i = 0; i < n; i++) 183 if (cnt[seg[i]] > 1) 184 ans[i] = 0; 185 186 for (int a : ans) 187 cout << a << '\n'; 188 } 189 190 int main() { 191 ios_base::sync_with_stdio(false); 192 cin.tie(0); 193 194 int t; cin >> t; 195 while (t--) 196 solve(); 197 return 0; 198 } 199 ``` 200 201 [2042E - Vertex Pairs](/contest/2042/problem/E "Educational Codeforces Round 172 (Rated for Div. 2)") 202 203 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 204 205 **Tutorial** 206 207 Tutorial is loading... 208 209 **Solution (awoo)** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 #define forn(i, n) for (int i = 0; i < int(n); i++) 215 216 using namespace std; 217 218 vector<vector<int>> g; 219 220 struct LCA { 221 vector<vector<pair<int, int>>> st; 222 vector<int> pw; 223 224 void build(vector<pair<int, int>> a) { 225 int n = a.size(); 226 int lg = 32 - __builtin_clz(n); 227 st.resize(lg, vector<pair<int, int>>(n)); 228 st[0] = a; 229 for (int j = 1; j < lg; ++j) { 230 for (int i = 0; i < n; ++i) { 231 st[j][i] = st[j - 1][i]; 232 if (i + (1 << (j - 1)) < n) 233 st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]); 234 } 235 } 236 pw.resize(n + 1); 237 for (int i = 2; i <= n; ++i) 238 pw[i] = pw[i / 2] + 1; 239 } 240 241 vector<int> d, fst, par; 242 vector<pair<int, int>> ord; 243 244 int lca(int v, int u) { 245 int l = fst[v], r = fst[u]; 246 if (l > r) swap(l, r); 247 ++r; 248 int len = pw[r - l]; 249 assert(len < int(st.size())); 250 return min(st[len][l], st[len][r - (1 << len)]).second; 251 } 252 253 void init(int v, int p = -1) { 254 if (fst[v] == -1) fst[v] = ord.size(); 255 ord.push_back({ d[v], v }); 256 for (int u : g[v]) if (u != p) { 257 par[u] = v; 258 d[u] = d[v] + 1; 259 init(u, v); 260 ord.push_back({ d[v], v }); 261 } 262 } 263 264 LCA(int r = 0) { 265 int n = g.size(); 266 d.resize(n); 267 fst.assign(n, -1); 268 par.assign(n, -1); 269 ord.clear(); 270 init(r); 271 272 build(ord); 273 } 274 }; 275 276 int main() { 277 cin.tie(0); 278 ios::sync_with_stdio(false); 279 int n; 280 cin >> n; 281 vector<int> a(2 * n); 282 forn(i, 2 * n){ 283 cin >> a[i]; 284 --a[i]; 285 } 286 g.resize(2 * n); 287 forn(i, 2 * n - 1){ 288 int v, u; 289 cin >> v >> u; 290 --v, --u; 291 g[v].push_back(u); 292 g[u].push_back(v); 293 } 294 vector<int> l(n, -1), r(n, -1); 295 forn(i, 2 * n){ 296 if (l[a[i]] == -1) l[a[i]] = i; 297 else r[a[i]] = i; 298 } 299 vector<char> res(2 * n, 1); 300 forn(rt, 2 * n) if (a[rt] == 0){ 301 LCA d(rt); 302 vector<int> state(2 * n, 0); 303 304 auto mark = [&](int v){ 305 while (v != -1 && state[v] != 1){ 306 state[v] = 1; 307 v = d.par[v]; 308 } 309 }; 310 auto markdel = [&](int v){ 311 queue<int> q; 312 q.push(v); 313 state[v] = -1; 314 while (!q.empty()){ 315 int v = q.front(); 316 q.pop(); 317 mark(l[a[v]] ^ r[a[v]] ^ v); 318 for (int u : g[v]) if (u != d.par[v] && state[u] == 0){ 319 state[u] = -1; 320 q.push(u); 321 } 322 } 323 }; 324 325 forn(i, n) mark(d.lca(l[i], r[i])); 326 for (int i = 2 * n - 1; i >= 0; --i) if (state[i] == 0) 327 markdel(i); 328 vector<char> cur(2 * n, 0); 329 for (int i = 0; i < 2 * n; ++i) if (state[i] == 1) 330 cur[i] = 1; 331 reverse(cur.begin(), cur.end()); 332 res = min(res, cur); 333 } 334 reverse(res.begin(), res.end()); 335 cout << count(res.begin(), res.end(), 1) << '\n'; 336 forn(i, 2 * n) if (res[i]) 337 cout << i + 1 << " "; 338 cout << '\n'; 339 return 0; 340 } 341 ``` 342 343 [2042F - Two Subarrays](/contest/2042/problem/F "Educational Codeforces Round 172 (Rated for Div. 2)") 344 345 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 346 347 **Tutorial** 348 349 Tutorial is loading... 350 351 **Solution (Neon)** 352 353 ``` 354 #include <bits/stdc++.h> 355 356 using namespace std; 357 358 #define forn(i, n) for (int i = 0; i < int(n); ++i) 359 360 const int N = 200 * 1000 + 13; 361 const int K = 5; 362 363 using li = long long; 364 using mat = array<array<li, K>, K>; 365 366 const li INF = 1e18; 367 368 int n, q; 369 li a[N], b[N]; 370 mat t[4 * N]; 371 372 mat init(li a, li b) { 373 mat c; 374 forn(i, K) forn(j, i + 1) c[j][i] = -INF; 375 c[0][0] = c[2][2] = c[4][4] = 0; 376 c[0][1] = c[2][3] = a + b; 377 c[0][2] = c[2][4] = a + b + b; 378 c[1][1] = c[3][3] = a; 379 c[1][2] = c[3][4] = a + b; 380 return c; 381 } 382 383 mat combine(mat a, mat b) { 384 mat c = init(-INF, -INF); 385 forn(i, K) forn(j, i + 1) forn(k, j + 1) 386 c[k][i] = max(c[k][i], a[k][j] + b[j][i]); 387 return c; 388 } 389 390 void build(int v, int l, int r) { 391 if (l + 1 == r) { 392 t[v] = init(a[l], b[l]); 393 return; 394 } 395 int m = (l + r) / 2; 396 build(v * 2 + 1, l, m); 397 build(v * 2 + 2, m, r); 398 t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]); 399 } 400 401 void upd(int v, int l, int r, int p) { 402 if (l + 1 == r) { 403 t[v] = init(a[l], b[l]); 404 return; 405 } 406 int m = (l + r) / 2; 407 if (p < m) upd(v * 2 + 1, l, m, p); 408 else upd(v * 2 + 2, m, r, p); 409 t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]); 410 } 411 412 mat get(int v, int l, int r, int L, int R) { 413 if (L >= R) return init(-INF, -INF); 414 if (l == L && r == R) return t[v]; 415 int m = (l + r) / 2; 416 return combine( 417 get(v * 2 + 1, l, m, L, min(m, R)), 418 get(v * 2 + 2, m, r, max(m, L), R) 419 ); 420 } 421 422 int main() { 423 ios::sync_with_stdio(false); cin.tie(0); 424 cin >> n; 425 forn(i, n) cin >> a[i]; 426 forn(i, n) cin >> b[i]; 427 build(0, 0, n); 428 cin >> q; 429 forn(_, q) { 430 int t, x, y; 431 cin >> t >> x >> y; 432 --x; 433 if (t == 1) { 434 a[x] = y; 435 upd(0, 0, n, x); 436 } else if (t == 2) { 437 b[x] = y; 438 upd(0, 0, n, x); 439 } else { 440 auto res = get(0, 0, n, x, y); 441 cout << res[0][4] << '\n'; 442 } 443 } 444 } 445 ```