1108.md (6981B)
1 Source: https://codeforces.com/blog/entry/64751 2 3 [1108A - Two distinct points](/contest/1108/problem/A "Codeforces Round 535 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int t; 18 cin >> t; 19 for (int i = 0; i < t; ++i) { 20 int l1, r1, l2, r2; 21 cin >> l1 >> r1 >> l2 >> r2; 22 vector<int>a({l1, r1, l2, r2}); 23 int ans1 = 0, ans2 = 0; 24 for (auto it : a) for (auto jt : a) { 25 if (l1 <= it && it <= r1 && l2 <= jt && jt <= r2 && it != jt) { 26 ans1 = it; 27 ans2 = jt; 28 } 29 } 30 cout << ans1 << " " << ans2 << endl; 31 } 32 33 return 0; 34 } 35 ``` 36 37 [1108B - Divisors of Two Integers](/contest/1108/problem/B "Codeforces Round 535 (Div. 3)") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 #ifdef _DEBUG 52 freopen("input.txt", "r", stdin); 53 // freopen("output.txt", "w", stdout); 54 #endif 55 56 int n; 57 cin >> n; 58 multiset<int> a; 59 for (int i = 0; i < n; ++i) { 60 int x; 61 cin >> x; 62 a.insert(x); 63 } 64 65 int x = *prev(a.end()); 66 for (int i = 1; i <= x; ++i) { 67 if (x % i == 0) { 68 a.erase(a.find(i)); 69 } 70 } 71 72 cout << x << " " << *prev(a.end()) << endl; 73 74 return 0; 75 } 76 ``` 77 78 [1108C - Nice Garland](/contest/1108/problem/C "Codeforces Round 535 (Div. 3)") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution** 85 86 ``` 87 #include <bits/stdc++.h> 88 89 using namespace std; 90 91 int main() { 92 #ifdef _DEBUG 93 freopen("input.txt", "r", stdin); 94 // freopen("output.txt", "w", stdout); 95 #endif 96 97 int n; 98 string s; 99 cin >> n >> s; 100 101 vector<int> p(3); 102 iota(p.begin(), p.end(), 0); 103 104 string colors = "RGB"; 105 string res = ""; 106 int ans = 1e9; 107 108 do { 109 string t; 110 int cnt = 0; 111 for (int i = 0; i < n; ++i) { 112 t += colors[p[i % 3]]; 113 cnt += t[i] != s[i]; 114 } 115 if (ans > cnt) { 116 ans = cnt; 117 res = t; 118 } 119 } while (next_permutation(p.begin(), p.end())); 120 121 cout << ans << endl << res << endl; 122 123 return 0; 124 } 125 ``` 126 127 [1108D - Diverse Garland](/contest/1108/problem/D "Codeforces Round 535 (Div. 3)") 128 129 **Tutorial** 130 131 Tutorial is loading... 132 133 **Solution** 134 135 ``` 136 #include <bits/stdc++.h> 137 138 using namespace std; 139 140 int main() { 141 #ifdef _DEBUG 142 freopen("input.txt", "r", stdin); 143 // freopen("output.txt", "w", stdout); 144 #endif 145 146 int n; 147 string s; 148 cin >> n >> s; 149 150 int ans = 0; 151 for (int i = 0; i < n; ++i) { 152 int j = i; 153 while (j < n && s[i] == s[j]) { 154 ++j; 155 } 156 string q = "RGB"; 157 q.erase(q.find(s[i]), 1); 158 if (j < n) q.erase(q.find(s[j]), 1); 159 for (int k = i + 1; k < j; k += 2) { 160 ++ans; 161 s[k] = q[0]; 162 } 163 i = j - 1; 164 } 165 166 cout << ans << endl << s << endl; 167 168 return 0; 169 } 170 ``` 171 172 [1108E1 - Array and Segments (Easy version)](/contest/1108/problem/E1 "Codeforces Round 535 (Div. 3)") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution** 179 180 ``` 181 #include <bits/stdc++.h> 182 183 using namespace std; 184 185 mt19937 rnd(time(NULL)); 186 187 const int INF = 1e9; 188 189 int main() { 190 #ifdef _DEBUG 191 freopen("input.txt", "r", stdin); 192 // freopen("output.txt", "w", stdout); 193 #endif 194 195 int n, m; 196 cin >> n >> m; 197 vector<int> a(n); 198 for (int i = 0; i < n; ++i) { 199 cin >> a[i]; 200 } 201 vector<pair<int, int>> b(m); 202 for (int i = 0; i < m; ++i) { 203 cin >> b[i].first >> b[i].second; 204 --b[i].first; 205 --b[i].second; 206 } 207 208 int ans = *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end()); 209 vector<int> res; 210 for (int i = 0; i < n; ++i) { 211 vector<int> add(n + 1); 212 vector<int> cur; 213 for (int j = 0; j < m; ++j) { 214 if (!(b[j].first <= i && i <= b[j].second)) { 215 cur.push_back(j); 216 for (int k = b[j].first; k <= b[j].second; ++k) { 217 --add[k]; 218 } 219 } 220 } 221 int mn = INF, mx = -INF; 222 for (int j = 0; j < n; ++j) { 223 mn = min(mn, a[j] + add[j]); 224 mx = max(mx, a[j] + add[j]); 225 } 226 if (ans < mx - mn) { 227 ans = mx - mn; 228 res = cur; 229 } 230 } 231 232 cout << ans << endl << res.size() << endl; 233 shuffle(res.begin(), res.end(), rnd); 234 for (auto it : res) cout << it + 1 << " "; 235 cout << endl; 236 237 return 0; 238 } 239 ``` 240 241 [1108E2 - Array and Segments (Hard version)](/contest/1108/problem/E2 "Codeforces Round 535 (Div. 3)") 242 243 **Tutorial** 244 245 Tutorial is loading... 246 247 **Solution** 248 249 ``` 250 #include <bits/stdc++.h> 251 252 using namespace std; 253 254 mt19937 rnd(time(NULL)); 255 256 const int INF = 1e9; 257 258 int main() { 259 #ifdef _DEBUG 260 freopen("input.txt", "r", stdin); 261 // freopen("output.txt", "w", stdout); 262 #endif 263 264 int n, m; 265 cin >> n >> m; 266 267 vector<int> a(n); 268 for (int i = 0; i < n; ++i) { 269 cin >> a[i]; 270 } 271 vector<pair<int, int>> b(m); 272 vector<vector<int>> lf(n), rg(n); 273 for (int i = 0; i < m; ++i) { 274 cin >> b[i].first >> b[i].second; 275 --b[i].first; 276 --b[i].second; 277 lf[b[i].second].push_back(b[i].first); 278 rg[b[i].first].push_back(b[i].second); 279 } 280 281 vector<int> ansv(n, -INF); 282 283 vector<int> add(n + 1 , 0); 284 int mn = a[0]; 285 286 for (int i = 0; i < n; ++i) { 287 ansv[i] = max(ansv[i], a[i] - mn); 288 for (auto l : lf[i]) { 289 for (int j = l; j <= i; ++j) { 290 --add[j]; 291 mn = min(mn, a[j] + add[j]); 292 } 293 } 294 mn = min(mn, a[i] + add[i]); 295 } 296 297 add = vector<int>(n + 1, 0); 298 mn = a[n - 1]; 299 300 for (int i = n - 1; i >= 0; --i) { 301 ansv[i] = max(ansv[i], a[i] - mn); 302 for (auto r : rg[i]) { 303 for (int j = i; j <= r; ++j) { 304 --add[j]; 305 mn = min(mn, a[j] + add[j]); 306 } 307 } 308 mn = min(mn, a[i] + add[i]); 309 } 310 311 int ans = *max_element(ansv.begin(), ansv.end()); 312 vector<int> res; 313 314 for (int i = 0; i < n; ++i) { 315 if (ansv[i] == ans) { 316 for (int j = 0; j < m; ++j) { 317 if (!(b[j].first <= i && i <= b[j].second)) { 318 res.push_back(j); 319 } 320 } 321 break; 322 } 323 } 324 325 cout << ans << endl << res.size() << endl; 326 shuffle(res.begin(), res.end(), rnd); 327 for (auto it : res) cout << it + 1 << " "; 328 cout << endl; 329 330 return 0; 331 } 332 ``` 333 334 [1108F - MST Unification](/contest/1108/problem/F "Codeforces Round 535 (Div. 3)") 335 336 **Tutorial** 337 338 Tutorial is loading... 339 340 **Solution** 341 342 ``` 343 #include <bits/stdc++.h> 344 345 using namespace std; 346 347 #define x first 348 #define y second 349 350 vector<int> p, rk; 351 352 int getp(int v) { 353 if (v == p[v]) return v; 354 return p[v] = getp(p[v]); 355 } 356 357 bool merge(int v, int u) { 358 u = getp(u); 359 v = getp(v); 360 361 if (u == v) return false; 362 363 if (rk[u] < rk[v]) swap(u, v); 364 365 rk[u] += rk[v]; 366 p[v] = u; 367 368 return true; 369 } 370 371 int main() { 372 #ifdef _DEBUG 373 freopen("input.txt", "r", stdin); 374 // freopen("output.txt", "w", stdout); 375 #endif 376 377 ios_base::sync_with_stdio(0); 378 int n, m; 379 cin >> n >> m; 380 381 p = vector<int>(n); 382 iota(p.begin(), p.end(), 0); 383 rk = vector<int>(n, 1); 384 385 vector<pair<pair<int, int>, int>> e(m); 386 for (int i = 0; i < m; ++i) { 387 cin >> e[i].x.x >> e[i].x.y >> e[i].y; 388 --e[i].x.x; 389 --e[i].x.y; 390 } 391 392 sort(e.begin(), e.end(), [](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) { 393 return a.y < b.y; 394 }); 395 396 int ans = 0; 397 for (int i = 0; i < m; ++i) { 398 int j = i; 399 while (j < m && e[i].y == e[j].y) { 400 ++j; 401 } 402 int cnt = j - i; 403 for (int k = i; k < j; ++k) { 404 if (getp(e[k].x.x) == getp(e[k].x.y)) { 405 --cnt; 406 } 407 } 408 for (int k = i; k < j; ++k) { 409 cnt -= merge(e[k].x.x, e[k].x.y); 410 } 411 ans += cnt; 412 i = j - 1; 413 } 414 415 cout << ans << endl; 416 417 return 0; 418 } 419 ```