codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```