codeforces-scrape

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

2111.md (14009B)


      1 Source: https://codeforces.com/blog/entry/143528
      2 
      3 Thank you for participating! I hope you enjoyed the problems.
      4 
      5 [2111A - Energy Crystals](/contest/2111/problem/A "Educational Codeforces Round 179 (Rated for Div. 2)")
      6 
      7 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution (FelixArg)**
     14 
     15 ```
     16 #include<bits/stdc++.h>
     17  
     18 using namespace std;
     19  
     20 #define int long long
     21  
     22 void solve(){
     23 	int x;
     24 	cin >> x;
     25 	int ans = 0;
     26 	int a1 = 0, a2 = 0, a3 = 0;
     27 	while(min({a1, a2, a3}) < x){
     28 		if (a1 <= a2 && a1 <= a3){
     29 			a1 = min(a2, a3) * 2 + 1;
     30 		}
     31 		else if (a2 <= a1 && a2 <= a3){
     32 			a2 = min(a1, a3) * 2 + 1;
     33 		}
     34 		else{
     35 			a3 = min(a1, a2) * 2 + 1;
     36 		}
     37 		ans++;
     38 	}
     39 	cout << ans << '\n';
     40 }
     41  
     42 signed main()
     43 {
     44 	ios_base::sync_with_stdio(false);
     45 	cin.tie(0);
     46 	cout.tie(0);
     47  
     48 	int tests = 1;
     49 	cin >> tests;
     50 	for (int test = 0; test < tests; test++){
     51 		solve();
     52 	}
     53 	return 0;
     54 }
     55 ```
     56 
     57 [2111B - Fibonacci Cubes](/contest/2111/problem/B "Educational Codeforces Round 179 (Rated for Div. 2)")
     58 
     59 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
     60 
     61 **Tutorial**
     62 
     63 Tutorial is loading...
     64 
     65 **Solution (FelixArg)**
     66 
     67 ```
     68 #include<bits/stdc++.h>
     69 using namespace std;
     70  
     71 #define int long long
     72  
     73 void solve(){
     74 	int n, m;
     75 	cin >> n >> m;
     76 	vector<vector<int>> a(m);
     77  
     78 	for (int i = 0; i < m; i++){
     79 		for (int j = 0; j < 3; j++){
     80 			int x;
     81 			cin >> x;
     82 			a[i].emplace_back(x);
     83 		}
     84 		sort(a[i].begin(), a[i].end());
     85 	}
     86 
     87 	vector<int> fib(n + 5);
     88 	fib[0] = 1;
     89 	fib[1] = 2;
     90 	for (int i = 2; i < n + 1; i++){
     91 		fib[i] = fib[i - 1] + fib[i - 2];
     92 	}
     93  
     94 	for (int i = 0; i < m; i++){
     95 		if (a[i][0] >= fib[n - 1] && a[i][1] >= fib[n - 1] && a[i][2] >= fib[n]){
     96 			cout << '1';
     97 		}
     98 		else{
     99 			cout << '0';
    100 		}
    101 	}
    102 	cout << '\n';
    103 }
    104  
    105 signed main()
    106 {
    107 	ios_base::sync_with_stdio(false);
    108 	cin.tie(0);
    109 	cout.tie(0);
    110  
    111 	int tests = 1;
    112 	cin >> tests;
    113 	for (int test = 0; test < tests; test++){
    114         solve();
    115 	}
    116 	return 0;
    117 }
    118 ```
    119 
    120 [2111C - Equal Values](/contest/2111/problem/C "Educational Codeforces Round 179 (Rated for Div. 2)")
    121 
    122 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Solution (awoo)**
    129 
    130 ```
    131 for _ in range(int(input())):
    132     n = int(input())
    133     a = list(map(int, input().split()))
    134     i = 0
    135     ans = 10**18
    136     while i < n:
    137         j = i
    138         while j < n and a[j] == a[i]:
    139             j += 1
    140         ans = min(ans, (i + n - j) * a[i])
    141         i = j
    142     print(ans)
    143 ```
    144 
    145 [2111D - Creating a Schedule](/contest/2111/problem/D "Educational Codeforces Round 179 (Rated for Div. 2)")
    146 
    147 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution (FelixArg)**
    154 
    155 ```
    156 #include<bits/stdc++.h>
    157  
    158 using namespace std;
    159  
    160 void solve(){
    161 	int n, m;
    162 	cin >> n >> m;
    163 	vector<int> a(m);
    164 	for (int i = 0; i < m; i++){
    165 		cin >> a[i];
    166 	}
    167 	sort(a.begin(), a.end());
    168 	vector<vector<int>> ans(n, vector<int> (6));
    169  
    170 	for (int i = 0; i < n; i += 2){
    171 		if (i + 1 == n){
    172 			for (int j = 0; j < 6; j++){
    173 				if (j % 2 == 0){
    174 					ans[i][j] = a[i / 2];
    175 				}
    176 				else{
    177 					ans[i][j] = a[m - i / 2 - 1];
    178 				}
    179 			}
    180 		}
    181 		else{
    182 			for (int j = 0; j < 6; j++){
    183 				if (j % 2 == 0){
    184 					ans[i][j] = a[i / 2];
    185 					ans[i + 1][j] = a[m - i / 2 - 1];
    186 				}
    187 				else{
    188 					ans[i][j] = a[m - i / 2 - 1];
    189 					ans[i + 1][j] = a[i / 2];
    190 				}
    191 			}
    192 		}
    193 	}
    194  
    195 	for (int i = 0; i < n; i++){
    196 		for (int j = 0; j < 6; j++){
    197 			cout << ans[i][j] << ' ';
    198 		}
    199 		cout << '\n';
    200 	}
    201 }
    202  
    203 signed main()
    204 {
    205 	ios_base::sync_with_stdio(false);
    206 	cin.tie(0);
    207 	cout.tie(0);
    208  
    209 	int tests = 1;
    210 	cin >> tests;
    211 	for (int test = 0; test < tests; test++){
    212 		solve();
    213 	}
    214 	return 0;
    215 }
    216 ```
    217 
    218 [2111E - Changing the String](/contest/2111/problem/E "Educational Codeforces Round 179 (Rated for Div. 2)")
    219 
    220 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (FelixArg)**
    227 
    228 ```
    229 #include<bits/stdc++.h>
    230 using namespace std;
    231  
    232 #define int long long
    233  
    234 void solve(){
    235 	int n, q;
    236 	cin >> n >> q;
    237 	string s;
    238 	cin >> s;
    239 	vector<vector<set<int>>> st(3, vector<set<int>> (3));
    240 	for (int i = 0; i < q; i++){
    241 		char x, y;
    242 		cin >> x >> y;
    243 		st[x - 'a'][y - 'a'].insert(i);
    244 	}
    245 
    246 	for (int i = 0; i < n; i++){
    247 		if (s[i] == 'a'){
    248 			continue;
    249 		}
    250 		
    251 		if (s[i] == 'b'){
    252 			if (!st[1][0].empty()){
    253 				st[1][0].erase(st[1][0].begin());
    254 				s[i] = 'a';
    255 				continue;
    256 			}
    257 			if (!st[1][2].empty()){
    258 				auto ind = *st[1][2].begin();
    259 				auto lb = st[2][0].lower_bound(ind);
    260 				if (lb != st[2][0].end()){
    261 					st[1][2].erase(ind);
    262 					st[2][0].erase(lb);
    263 					s[i] = 'a';
    264 					continue;
    265 				}
    266 			}
    267 		}
    268 
    269 		if (s[i] == 'c'){
    270 			if (!st[2][0].empty()){
    271 				st[2][0].erase(st[2][0].begin());
    272 				s[i] = 'a';
    273 				continue;
    274 			}
    275 			if (!st[2][1].empty()){
    276 				auto ind = *st[2][1].begin();
    277 				st[2][1].erase(ind);
    278 				s[i] = 'b';
    279 				auto lb = st[1][0].lower_bound(ind);
    280 				if (lb != st[1][0].end()){
    281 					st[1][0].erase(lb);
    282 					s[i] = 'a';
    283 				}
    284 			}
    285 		}
    286 	}
    287 
    288 	cout << s << '\n';
    289 }
    290  
    291 signed main()
    292 {
    293 	ios_base::sync_with_stdio(false);
    294 	cin.tie(0);
    295 	cout.tie(0);
    296  
    297 	int tests = 1;
    298 	cin >> tests;
    299 	for (int test = 0; test < tests; test++){
    300                 solve();
    301 	}
    302 	return 0;
    303 }
    304 ```
    305 
    306 [2111F - Puzzle](/contest/2111/problem/F "Educational Codeforces Round 179 (Rated for Div. 2)")
    307 
    308 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    309 
    310 **Tutorial**
    311 
    312 Tutorial is loading...
    313 
    314 **Solution (FelixArg)**
    315 
    316 ```
    317 #include<bits/stdc++.h>
    318 using namespace std;
    319 
    320 #define int long long
    321  
    322 void solve(){
    323 	int p, s;
    324 	cin >> p >> s;
    325 
    326 	if (p > 4 * s){
    327 		cout << "-1\n";
    328 		return;
    329 	}
    330 	if (p > 2 * s){
    331 		for (int i = 1; i <= 50000; i++){
    332 			if (p * i == (2 + 2 * i) * s){
    333 				cout << i << '\n';
    334 				for (int j = 0; j < i; j++){
    335 					cout << "0 " << j << '\n';
    336 				}
    337 				return;
    338 			}
    339 		}
    340 		cout << "-1\n";
    341 		return;
    342 	}
    343 
    344 	int k = 0;
    345 	while(p > 2){
    346 		p -= 2;
    347 		s -= 1;
    348 		k++;
    349 	}
    350 
    351 	if (p == 2){
    352 		cout << 4 * s * s + 4 * s * k << '\n';
    353 		for (int i = 0; i < 2 * s; i++){
    354 			for (int j = 0; j < 2 * s; j++){
    355 				cout << i << ' ' << j << '\n';
    356 			}
    357 		}
    358 		for (int i = 0; i < 4 * s * k; i++){
    359 			cout << 0 << ' ' << 2 * s + i << '\n';
    360 		}
    361 	}
    362 	else{
    363 		cout << 16 * s * s + 16 * s * k << '\n';
    364 		for (int i = 0; i < 4 * s; i++){
    365 			for (int j = 0; j < 4 * s; j++){
    366 				cout << i << ' ' << j << '\n';
    367 			}
    368 		}
    369 		for (int i = 0; i < 16 * s * k; i++){
    370 			cout << 0 << ' ' << 4 * s + i << '\n';
    371 		}
    372 	}
    373 }
    374  
    375 signed main()
    376 {
    377 	ios_base::sync_with_stdio(false);
    378 	cin.tie(0);
    379 	cout.tie(0);
    380  
    381 	int tests = 1;
    382 	cin >> tests;
    383 	for (int test = 0; test < tests; test++){
    384         solve();
    385 	}
    386 	return 0;
    387 }
    388 ```
    389 
    390 [2111G - Divisible Subarrays](/contest/2111/problem/G "Educational Codeforces Round 179 (Rated for Div. 2)")
    391 
    392 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg")
    393 
    394 **Tutorial**
    395 
    396 Tutorial is loading...
    397 
    398 **Solution (FelixArg)**
    399 
    400 ```
    401 #include<bits/stdc++.h>
    402  
    403 using namespace std;
    404  
    405 struct PersistentSegmentTree{
    406 	#define _null -1
    407 	struct Node{
    408 		int l, r;
    409 		int val;
    410 		Node(): l(-1), r(-1), val(_null) {}
    411 	};
    412 	vector<Node> data;
    413 	vector<int> roots;
    414 	PersistentSegmentTree(){}
    415  
    416 	inline void copy(int x, int y){
    417 		data[x].l = data[y].l;
    418 		data[x].r = data[y].r;
    419 		data[x].val = data[y].val;
    420 	}
    421  
    422 	int build(int v, int l, int r, vector<int>& a){
    423 		if (data.size() == v){
    424 			data.emplace_back();
    425 		}
    426 		if (l == r){
    427 			data[v].val = a[l];
    428 			return v;
    429 		}
    430 		int m = (l + r) / 2;
    431 		data[v].l = build(data.size(), l, m, a);
    432 		data[v].r = build(data.size(), m + 1, r, a);
    433 		data[v].val = max(data[data[v].l].val, data[data[v].r].val);
    434 		return v;
    435 	}
    436  
    437 	int update(int v, int l, int r, int pos, int val){
    438 		int new_v = data.size();
    439 		data.emplace_back();
    440 		copy(new_v, v);
    441 		if (l == r){
    442 			data[new_v].val = val;
    443 			return new_v;
    444 		}
    445 		int m = (l + r) / 2;
    446 		if (pos <= m){
    447 			data[new_v].l = update(data[v].l, l, m, pos, val);
    448 		}
    449 		else{
    450 			data[new_v].r = update(data[v].r, m + 1, r, pos, val);
    451 		}
    452 		data[new_v].val = max(data[data[new_v].l].val, data[data[new_v].r].val);
    453 		return new_v;
    454 	}
    455  
    456 	int get(int v, int l, int r, int ql, int qr){
    457 		if (ql > qr){
    458 			return _null;
    459 		}
    460 		if (l == ql && r == qr){
    461 			return data[v].val;
    462 		}
    463 		int m = (l + r) / 2;
    464 		return max(get(data[v].l, l, m, ql, min(qr, m)), 
    465 			get(data[v].r, m + 1, r, max(ql, m + 1), qr));
    466 	}
    467 };
    468  
    469 void solve(){
    470 	int n;
    471 	cin >> n;
    472  
    473 	vector<int> p(n);
    474 	for(int i = 0; i < n; i++){
    475 		cin >> p[i];
    476 		p[i]--;
    477 	}
    478  
    479 	vector<pair<int,int>> p2(n);
    480 	for (int i = 0; i < n; i++){
    481 		p2[i] = {p[i], i};
    482 	}
    483 	sort(p2.begin(), p2.end());
    484  
    485 	vector<tuple<int,int,int,int>> seg;
    486 	set<pair<int,int>> st;
    487  
    488 	st.insert({-2, -2});
    489 	st.insert({n + 1, n + 1});
    490  
    491 	for (int i = 0; i < n; i++){
    492 		auto [val, ind] = p2[i];
    493 		auto up = st.lower_bound(pair{ind, -1});
    494 		auto down = (--st.lower_bound(pair{ind, -1}));
    495  
    496 		int l, r;
    497  
    498 		if (down->second == ind - 1 && up->first == ind + 1){
    499 			l = down->first, r = up->second;
    500 			st.erase(up);
    501 			st.erase(down);
    502 		}
    503 		else if (down->second == ind - 1){
    504 			l = down->first, r = down->second + 1;
    505 			st.erase(down);
    506 		}
    507 		else if (up->first == ind + 1){
    508 			l = up->first - 1, r = up->second;
    509 			st.erase(up);
    510 		}
    511 		else{
    512 			l = ind, r = ind;
    513 		}
    514 		st.insert({l, r});
    515  
    516 		up = st.lower_bound(pair{l + 1, -1});
    517 		down = (--st.lower_bound(pair{l, -1}));
    518  
    519 		if (l > 0){
    520 			seg.emplace_back(max(0, down->second + 1), l - 1, r, i * 2);
    521 		}
    522 		if (r < n - 1){
    523 			seg.emplace_back(l, r, min(n - 1, up->first - 1), i * 2 + 1);
    524 		}
    525 	}
    526  
    527 	sort(seg.begin(), seg.end());
    528  
    529 	vector<tuple<int,int,int>> seg2;
    530 	for (int i = 0; i < seg.size(); i++){
    531 		auto [l1, r1, r2, ind] = seg[i];
    532 		seg2.emplace_back(r1 + 1, r2, ind);
    533 	}
    534 	sort(seg2.begin(), seg2.end());
    535  
    536 	vector<int> pos(2 * n, -1);
    537 	for (int i = 0; i < seg2.size(); i++){
    538 		auto [l, r, ind] = seg2[i];
    539 		pos[ind] = i;
    540 	}
    541  
    542 	set<pair<int,int>> open_left_segs;
    543  
    544 	vector<int> cur(2 * n, -1);
    545 	PersistentSegmentTree tree;
    546 	tree.roots.emplace_back(tree.build(0, 0, 2 * n - 1, cur));
    547  
    548 	vector<int> T(n, -1);
    549 	int u = 0;
    550 	for (int i = 0; i < n; i++){
    551 		while(u < seg.size() && get<0>(seg[u]) <= i){
    552 			auto [l1, r1, r2, ind] = seg[u];
    553 			open_left_segs.insert({r1, pos[ind]});
    554 			tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, pos[ind], r2));
    555 			u++;
    556 		}
    557 		while(!open_left_segs.empty() && open_left_segs.begin()->first < i){
    558 			auto [r, ind] = *open_left_segs.begin();
    559 			open_left_segs.erase(open_left_segs.begin());
    560 			tree.roots.emplace_back(tree.update(tree.roots.back(), 0, 2 * n - 1, ind, -1));
    561 		}
    562 		T[i] = tree.roots.back();
    563 	}
    564  
    565 	int q;
    566 	cin >> q;
    567 	for (int i = 0; i < q; i++){
    568 		if (i % 10 == 0){
    569 			cout.flush();
    570 		}
    571 		int l, r;
    572 		cin >> l >> r;
    573 		l--;
    574 		r--;
    575 		auto lb = lower_bound(seg2.begin(), seg2.end(), tuple{l + 1, -1, -1});
    576 		if (lb == seg2.end()){
    577 			cout << "NO\n";
    578 			continue;
    579 		}
    580 		auto lb2 = lower_bound(seg2.begin(), seg2.end(), tuple{r + 1, -1, -1});
    581  
    582 		int val;
    583 		if (lb2 == seg2.end()){
    584 			val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], 2 * n - 1);
    585 		}
    586 		else{
    587 			val = tree.get(T[l], 0, 2 * n - 1, pos[get<2>(*lb)], pos[get<2>(*lb2)] - 1);
    588 		}
    589 		cout << (val >= r ? "YES\n" : "NO\n");
    590 	}
    591 	cout.flush();
    592 }
    593  
    594 signed main()
    595 {
    596 	ios_base::sync_with_stdio(false);
    597 	cin.tie(0);
    598 	cout.tie(0);
    599  
    600 	int tests = 1;
    601 	//cin >> tests;
    602 	for (int test = 0; test < tests; test++){
    603 		solve();
    604 	}
    605 	return 0;
    606 }
    607 ```
    608 
    609 **Solution (awoo)**
    610 
    611 ```
    612 #include <bits/stdc++.h>
    613 
    614 using namespace std;
    615 
    616 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    617 
    618 const int INF = 1e9;
    619 const int LOGN = 18;
    620 
    621 struct solver{
    622     int n;
    623     vector<int> p;
    624 
    625     solver(const vector<int> &p) : p(p){
    626         n = p.size();
    627         build();
    628     }
    629 
    630     vector<int> nxtmn, nxtmx;
    631 
    632     vector<vector<int>> up;
    633     vector<vector<int>> mx;
    634 
    635     void build(){
    636         nxtmx.resize(n);
    637         vector<int> stmn, stmx;
    638         for (int i = n - 1; i >= 0; --i){
    639             while (!stmx.empty() && p[stmx.back()] < p[i])
    640                 stmx.pop_back();
    641             nxtmx[i] = (stmx.empty() ? n : stmx.back());
    642             stmx.push_back(i);
    643         }
    644         vector<vector<int>> qr(n + 1);
    645         forn(i, n) qr[nxtmx[i]].push_back(i);
    646         nxtmn.assign(n, n);
    647         for (int i = n - 1; i >= 0; --i){
    648             while (!stmn.empty() && p[stmn.back()] > p[i])
    649                 stmn.pop_back();
    650             stmn.push_back(i);
    651             for (int j : qr[i]){
    652                 int l = 0, r = int(stmn.size()) - 1;
    653                 while (l <= r){
    654                     int m = (l + r) / 2;
    655                     if (p[stmn[m]] < p[j]){
    656                         nxtmn[j] = stmn[m];
    657                         l = m + 1;
    658                     }
    659                     else{
    660                         r = m - 1;
    661                     }
    662                 }
    663             }
    664         }
    665         up.assign(n + 1, vector<int>(LOGN));
    666         mx.assign(n + 1, vector<int>(LOGN));
    667         forn(i, n){
    668             up[i][0] = nxtmx[i];
    669             mx[i][0] = nxtmn[i];
    670         }
    671         up[n][0] = n;
    672         mx[n][0] = 0;
    673         for (int j = 1; j < LOGN; ++j) forn(i, n + 1){
    674             up[i][j] = up[up[i][j - 1]][j - 1];
    675             mx[i][j] = max(mx[i][j - 1], mx[up[i][j - 1]][j - 1]);
    676         }
    677     }
    678 
    679     bool query(int l, int r){
    680         int v = l;
    681         for (int i = LOGN - 1; i >= 0; --i){
    682             if (up[v][i] >= r) continue;
    683             if (mx[v][i] >= r) return true;
    684             v = up[v][i];
    685         }
    686         return false;
    687     }
    688 };
    689 
    690 int main(){
    691 #ifdef _DEBUG
    692     freopen("input.txt", "r", stdin);
    693 #endif
    694     cin.tie(0);
    695     ios::sync_with_stdio(false);
    696     int n;
    697     cin >> n;
    698     vector<vector<int>> p(2, vector<int>(n));
    699     forn(i, n){
    700         cin >> p[0][i];
    701         --p[0][i];
    702     }
    703     p[1] = p[0];
    704     reverse(p[1].begin(), p[1].end());
    705     solver p0(p[0]);
    706     solver p1(p[1]);
    707     int m;
    708     cin >> m;
    709     forn(i, m){
    710 		if (i % 10 == 0){
    711 			cout.flush();
    712 		}
    713         int l, r;
    714         cin >> l >> r;
    715         --l; -- r;
    716         bool ans = p0.query(l, r + 1) || p1.query(n - r - 1, n - l);
    717         cout << (ans ? "YES\n" : "NO\n");
    718     }
    719     cout.flush();
    720 }
    721 ```