codeforces-scrape

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

1093.md (11597B)


      1 Source: https://codeforces.com/blog/entry/63877
      2 
      3 [1093A - Dice Rolling](/contest/1093/problem/A "Educational Codeforces Round 56 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     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 x;
     21 		cin >> x;
     22 		cout << x / 2 << endl;
     23 	}
     24 	return 0;
     25 }
     26 ```
     27 
     28 [1093B - Letters Rearranging](/contest/1093/problem/B "Educational Codeforces Round 56 (Rated for Div. 2)")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (Vovuh)**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 int main() {
     42 	int t;
     43 	cin >> t;
     44 	for (int i = 0; i < t; ++i) {
     45 		string s;
     46 		cin >> s;
     47 		sort(s.begin(), s.end());
     48 		if (s[0] == s.back()) cout << -1 << endl;
     49 		else cout << s << endl;
     50 	}
     51 	return 0;
     52 }
     53 ```
     54 
     55 [1093C - Mishka and the Last Exam](/contest/1093/problem/C "Educational Codeforces Round 56 (Rated for Div. 2)")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (PikMike)**
     62 
     63 ```
     64 n = int(input())
     65 l, r = 0, 10**18
     66 b = list(map(int, input().split()))
     67 a = [0 for i in range(n)]
     68 for i in range(n // 2):
     69 	a[i] = max(l, b[i] - r)
     70 	a[-i - 1] = b[i] - a[i]
     71 	l, r = a[i], a[-i - 1]
     72 print(*a)
     73 ```
     74 
     75 **Naive (PikMike)**
     76 
     77 ```
     78 #include <bits/stdc++.h>
     79 
     80 #define forn(i, n) for (int i = 0; i < int(n); i++)
     81 
     82 using namespace std;
     83 
     84 const long long INF64 = 1'000'000'000'000'000'000ll;
     85 const int N = 200 * 1000 + 13;
     86 
     87 int n;
     88 long long a[N], b[N];
     89 
     90 void brute(int x, long long l, long long r){
     91 	if (x == n / 2){
     92 		forn(i, n)
     93 			printf("%lld ", a[i]);
     94 		puts("");
     95 		exit(0);
     96 	}
     97 	
     98 	for (long long i = l; i <= b[x] / 2; ++i) if (b[x] - i <= r){
     99 		a[x] = i;
    100 		a[n - x - 1] = b[x] - i;
    101 		brute(x + 1, i, b[x] - i);
    102 	}
    103 }
    104 
    105 int main() {
    106 	scanf("%d", &n);
    107 	forn(i, n / 2)
    108 		scanf("%lld", &b[i]);
    109 	brute(0, 0, INF64);
    110 	return 0;
    111 }
    112 ```
    113 
    114 [1093D - Beautiful Graph](/contest/1093/problem/D "Educational Codeforces Round 56 (Rated for Div. 2)")
    115 
    116 **Tutorial**
    117 
    118 Tutorial is loading...
    119 
    120 **Solution (Ajosteen)**
    121 
    122 ```
    123 #include <bits/stdc++.h>
    124 
    125 using namespace std;
    126 
    127 const int N = int(3e5) + 999;
    128 const int MOD = 998244353;
    129 
    130 int n, m;
    131 vector <int> g[N];
    132 int p2[N];
    133 int cnt[2];
    134 int col[N];
    135 bool bad;
    136 
    137 void dfs(int v, int c){
    138 	col[v] = c;
    139 	++cnt[c];
    140 	for(auto to : g[v]){
    141 		if(col[to] == -1) dfs(to, 1 - c);
    142 		if((col[v] ^ col[to]) == 0)
    143 			bad = true;
    144 	}
    145 }
    146 
    147 int main() {
    148     p2[0] = 1;
    149     for(int i = 1; i < N; ++i)
    150     	p2[i] = (2 * p2[i - 1]) % MOD;
    151     	
    152     int tc;
    153     scanf("%d", &tc);
    154     while(tc--){
    155     	scanf("%d%d", &n, &m);
    156     	for(int i = 0; i < n; ++i)
    157     	    g[i].clear();
    158     	
    159     	for(int i = 0; i < m; ++i){
    160     		int u, v;
    161     		scanf("%d %d", &u, &v);
    162     		--u, --v;
    163     		g[u].push_back(v);
    164     		g[v].push_back(u);
    165     	}
    166     	
    167     	int res = 1;
    168     	for(int i = 0; i < n; ++i) col[i] = -1;
    169     	for(int i = 0; i < n; ++i){
    170     	    if(col[i] != -1) continue;
    171             bad = false;
    172             cnt[0] = cnt[1] = 0;
    173             dfs(i, 0);
    174     	    if(bad){
    175     		    puts("0");
    176     		    break;
    177     	    }
    178     	    int cur = (p2[cnt[0]] + p2[cnt[1]]) % MOD;
    179     	    res = (res * 1LL * cur) % MOD;
    180     	}
    181     	
    182     	if(!bad) printf("%d\n", res);
    183     }
    184     
    185     return 0;
    186 }
    187 ```
    188 
    189 [1093E - Intersection of Permutations](/contest/1093/problem/E "Educational Codeforces Round 56 (Rated for Div. 2)")
    190 
    191 **Tutorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution (PikMike)**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199 
    200 #define forn(i, n) for (int i = 0; i < int(n); i++)
    201 
    202 using namespace std;
    203 
    204 const int N = 200 * 1000 + 13;
    205 
    206 int n, m;
    207 int a[N], b[N], pos[N];
    208 
    209 vector<int> f[N];
    210 vector<int> vals[N];
    211 
    212 void addupd(int x, int y){
    213 	for (int i = x; i < N; i |= i + 1)
    214 		vals[i].push_back(y);
    215 }
    216 
    217 void addget(int x, int y){
    218 	if (x < 0 || y < 0) return;
    219 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    220 		vals[i].push_back(y);
    221 }
    222 
    223 void upd(int x, int y, int val){
    224 	for (int i = x; i < N; i |= i + 1)
    225 		for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < int(f[i].size()); j |= j + 1)
    226 			f[i][j] += val;
    227 }
    228 
    229 int get(int x, int y){
    230 	if (x < 0 || y < 0) return 0;
    231 	int res = 0;
    232 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    233 		for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j >= 0; j = (j & (j + 1)) - 1)
    234 			res += f[i][j];
    235 	return res;
    236 }
    237 
    238 struct query{
    239 	int t, la, ra, lb, rb;
    240 	query(){};
    241 };
    242 
    243 query q[N];
    244 
    245 int main() {
    246 	scanf("%d%d", &n, &m);
    247 	
    248 	forn(i, n){
    249 		scanf("%d", &a[i]);
    250 		--a[i];
    251 		pos[a[i]] = i;
    252 	}
    253 	
    254 	forn(i, n){
    255 		scanf("%d", &b[i]);
    256 		--b[i];
    257 		b[i] = pos[b[i]];
    258 	}
    259 	
    260 	forn(i, m){
    261 		scanf("%d", &q[i].t);
    262 		if (q[i].t == 1){
    263 			scanf("%d%d%d%d", &q[i].la, &q[i].ra, &q[i].lb, &q[i].rb);
    264 			--q[i].la, --q[i].ra, --q[i].lb, --q[i].rb;
    265 		}
    266 		else{
    267 			scanf("%d%d", &q[i].lb, &q[i].rb);
    268 			--q[i].lb, --q[i].rb;
    269 		}
    270 	}
    271 	
    272 	vector<int> tmp(b, b + n);
    273 	
    274 	forn(i, n) addupd(i, b[i]);
    275 	forn(i, m){
    276 		if (q[i].t == 1){
    277 			addget(q[i].rb, q[i].ra);
    278 			addget(q[i].lb - 1, q[i].ra);
    279 			addget(q[i].rb, q[i].la - 1);
    280 			addget(q[i].lb - 1, q[i].la - 1);
    281 		}
    282 		else{
    283 			addupd(q[i].lb, b[q[i].lb]);
    284 			addupd(q[i].rb, b[q[i].rb]);
    285 			swap(b[q[i].lb], b[q[i].rb]);
    286 			addupd(q[i].lb, b[q[i].lb]);
    287 			addupd(q[i].rb, b[q[i].rb]);
    288 		}
    289 	}
    290 	
    291 	forn(i, n) b[i] = tmp[i];
    292 	
    293 	forn(i, N){
    294 		sort(vals[i].begin(), vals[i].end());
    295 		vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
    296 		f[i].resize(vals[i].size(), 0);
    297 	}
    298 	
    299 	forn(i, n)
    300 		upd(i, b[i], 1);
    301 	
    302 	forn(i, m){
    303 		if (q[i].t == 1){
    304 			int res = 0;
    305 			res += get(q[i].rb, q[i].ra);
    306 			res -= get(q[i].lb - 1, q[i].ra);
    307 			res -= get(q[i].rb, q[i].la - 1);
    308 			res += get(q[i].lb - 1, q[i].la - 1);
    309 			printf("%d\n", res);
    310 		}
    311 		else{
    312 			upd(q[i].lb, b[q[i].lb], -1);
    313 			upd(q[i].rb, b[q[i].rb], -1);
    314 			swap(b[q[i].lb], b[q[i].rb]);
    315 			upd(q[i].lb, b[q[i].lb], 1);
    316 			upd(q[i].rb, b[q[i].rb], 1);
    317 		}
    318 	}
    319 	return 0;
    320 }
    321 ```
    322 
    323 [1093F - Vasya and Array](/contest/1093/problem/F "Educational Codeforces Round 56 (Rated for Div. 2)")
    324 
    325 **Tutorial**
    326 
    327 Tutorial is loading...
    328 
    329 **Solution (Ajosteen)**
    330 
    331 ```
    332 #include <bits/stdc++.h>
    333 
    334 #define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
    335 #define forn(i, n) fore(i, 0, n)
    336 #define nfor(i, n) for(int i = int(n) - 1; i >= 0; --i)
    337 #define for1(i, n) for(int i = 1; i < int(n); ++i)
    338 
    339 #define mp make_pair
    340 #define pb push_back
    341 #define sz(a) int((a).size())
    342 #define all(a) (a).begin(), (a).end()
    343 #define x first
    344 #define y second
    345 
    346 #define correct(x, y, xmax, ymax) ((x) >= 0 && (x) < (xmax) && (y) >= 0 && (y) < (ymax))
    347 #define max(a, b) ((a > b)? a : b)
    348 #define min(a, b) ((a < b)? a : b)
    349 #define abs(a) ((a < 0) ? -a : a)
    350 #define sqr(a) (a * a)
    351 
    352 using namespace std;
    353 
    354 const int N = int(1e5);
    355 const int M = 105;
    356 const int MOD = 998244353;
    357 
    358 int sum(int a, int b){
    359 	return (a + b) % MOD;	
    360 }
    361 
    362 int n, k, len;
    363 int a[N];
    364 int dp[N][M];
    365 int sumdp[N];
    366 int cnt[M][N];
    367 
    368 int main() {
    369 	scanf("%d %d %d", &n, &k, &len);
    370 	forn(i, n){ 	
    371 		scanf("%d", a + i);
    372 		if(a[i] != -1) --a[i];
    373 	}
    374     forn(i, k) 
    375         forn(j, n)
    376             cnt[i][j + 1] = cnt[i][j] + (a[j] == i || a[j] == -1);
    377             
    378 	forn(i, n){ 
    379 		forn(j, k){
    380 			if(!(a[i] == -1 || a[i] == j))
    381 				continue;
    382 			
    383 			int add = 1;
    384 			if(i > 0) add = sumdp[i - 1];
    385 			dp[i][j] = add;
    386 			
    387 			bool ok = i + 1 >= len;
    388 			int l = max(0, i - len + 1);
    389 			int r = i + 1;
    390 			ok &= (r - l == cnt[j][r] - cnt[j][l]); 
    391 			if(!ok) continue;
    392 			
    393 			if(i + 1 == len){
    394 				dp[i][j] = sum(dp[i][j], MOD - 1);
    395 				continue;
    396 			}
    397 			
    398 			add = sum(dp[i - len][j], MOD - sumdp[i - len]);
    399 			dp[i][j] = sum(dp[i][j], add);
    400 		}
    401 		forn(j, k) sumdp[i] = sum(sumdp[i], dp[i][j]);
    402 	}
    403 	
    404 	printf("%d\n", sumdp[n - 1]);
    405 
    406 	return 0;
    407 }
    408 ```
    409 
    410 [1093G - Multidimensional Queries](/contest/1093/problem/G "Educational Codeforces Round 56 (Rated for Div. 2)")
    411 
    412 **Tutorial**
    413 
    414 Tutorial is loading...
    415 
    416 **Solution (BledDest)**
    417 
    418 ```
    419 #include <bits/stdc++.h>
    420 
    421 using namespace std;
    422 
    423 const int N = 200043;
    424 const int INF = int(1e9);
    425 
    426 int T[4 * N][32];
    427 int A[4 * N][5];
    428 int n, k;
    429 
    430 void build(int v, int l, int r)
    431 {
    432 	if(l == r - 1)
    433 	{
    434 		for(int i = 0; i < (1 << k); i++)
    435 		{
    436 			int cur = 0;
    437 			for(int j = 0; j < k; j++)
    438 				if(i & (1 << j))
    439 					cur += A[l][j];
    440 				else
    441 					cur -= A[l][j];
    442 			T[v][i] = cur;
    443 		}
    444 	}
    445 	else
    446 	{
    447 		int m = (l + r) / 2;
    448 		build(v * 2 + 1, l, m);
    449 		build(v * 2 + 2, m, r);
    450 		for(int i = 0; i < (1 << k); i++)
    451 			T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]);
    452 	}
    453 }
    454 
    455 int query(int v, int l, int r, int L, int R, int x)
    456 {
    457 	if(L >= R) return INF;
    458 	if(L == l && R == r)
    459 		return T[v][x];
    460 	int m = (l + r) / 2;
    461 	return min(query(v * 2 + 1, l, m, L, min(R, m), x), query(v * 2 + 2, m, r, max(L, m), R, x));
    462 }
    463 
    464 void upd(int v, int l, int r, int z)
    465 {
    466 	if(l == r - 1)
    467 	{
    468 		for(int i = 0; i < (1 << k); i++)
    469 		{
    470 			int cur = 0;
    471 			for(int j = 0; j < k; j++)
    472 				if(i & (1 << j))
    473 					cur += A[l][j];
    474 				else
    475 					cur -= A[l][j];
    476 			T[v][i] = cur;
    477 		}
    478 	}
    479 	else
    480 	{
    481 		int m = (l + r) / 2;
    482 		if(z < m)
    483 			upd(v * 2 + 1, l, m, z);
    484 		else
    485 			upd(v * 2 + 2, m, r, z);
    486 		for(int i = 0; i < (1 << k); i++)
    487 			T[v][i] = min(T[v * 2 + 1][i], T[v * 2 + 2][i]);
    488 	}
    489 }
    490 
    491 int main() 
    492 { 
    493 	scanf("%d %d", &n, &k);
    494 	for(int i = 0; i < n; i++)
    495 	{
    496 		for(int j = 0; j < k; j++)
    497 		{
    498 			scanf("%d", &A[i][j]);
    499 		}
    500 	}
    501 	int q;
    502 	scanf("%d", &q);
    503 	build(0, 0, n);
    504 	for(int i = 0; i < q; i++)
    505 	{
    506 		int t;
    507 		scanf("%d", &t);
    508 		if(t == 1)
    509 		{
    510 			int z;
    511 			scanf("%d", &z);
    512 			--z;
    513 			for(int j = 0; j < k; j++)
    514 				scanf("%d", &A[z][j]);
    515 			upd(0, 0, n, z);
    516 		}
    517 		else
    518 		{
    519 			int ans = 0;
    520 			int l, r;
    521 			scanf("%d %d", &l, &r);
    522 			--l;
    523 			for(int i = 0; i < (1 << (k - 1)); i++)
    524 			{
    525 				int x = query(0, 0, n, l, r, i);
    526 				int y = query(0, 0, n, l, r, ((1 << k) - 1) ^ i);
    527 				ans = max(ans, abs(x + y));
    528 			}
    529 			printf("%d\n", ans);
    530 		}
    531 	}
    532 	return 0;
    533 }
    534 ```
    535 
    536 **Solution (PikMike)**
    537 
    538 ```
    539 #include <bits/stdc++.h>
    540 
    541 #define forn(i, n) for (int i = 0; i < int(n); i++)
    542 
    543 using namespace std;
    544 
    545 const int N = 200 * 1000 + 13;
    546 const int INF = 1e9;
    547 
    548 struct point{
    549 	int a[5];
    550 	point(){};
    551 	int& operator[](int x){
    552 		return a[x];
    553 	}
    554 };
    555 
    556 int n, k;
    557 point a[N];
    558 
    559 int t[32][4 * N];
    560 
    561 int apply(point& p, int mask){
    562 	int res = 0;
    563 	forn(i, k){
    564 		res += (mask & 1 ? p[i] : -p[i]);
    565 		mask >>= 1;
    566 	}
    567 	return res;
    568 }
    569 
    570 void build(int v, int l, int r){
    571 	if (l == r - 1){
    572 		forn(mask, 1 << k)
    573 			t[mask][v] = apply(a[l], mask);
    574 		return;
    575 	}
    576 	
    577 	int m = (l + r) / 2;
    578 	
    579 	build(v * 2, l, m);
    580 	build(v * 2 + 1, m, r);
    581 	
    582 	forn(mask, 1 << k)
    583 		t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]);
    584 }
    585 
    586 void upd(int v, int l, int r, int pos, point& val){
    587 	if (l == r - 1){
    588 		forn(mask, 1 << k)
    589 			t[mask][v] = apply(val, mask);
    590 		return;
    591 	}
    592 	
    593 	int m = (l + r) / 2;
    594 	
    595 	if (pos < m)
    596 		upd(v * 2, l, m, pos, val);
    597 	else
    598 		upd(v * 2 + 1, m, r, pos, val);
    599 	
    600 	forn(mask, 1 << k)
    601 		t[mask][v] = min(t[mask][v * 2], t[mask][v * 2 + 1]);
    602 }
    603 
    604 int bst[32];
    605 
    606 void get(int v, int l, int r, int L, int R){
    607 	if (L >= R)
    608 		return;
    609 	
    610 	if (l == L && r == R){
    611 		forn(mask, 1 << k)
    612 			bst[mask] = min(bst[mask], t[mask][v]);
    613 		return;
    614 	}
    615 	
    616 	int m = (l + r) / 2;
    617 	
    618 	get(v * 2, l, m, L, min(m, R));
    619 	get(v * 2 + 1, m, r, max(m, L), R);
    620 }
    621 
    622 int main() {
    623 	scanf("%d%d", &n, &k);
    624 	forn(i, n) forn(j, k)
    625 		scanf("%d", &a[i][j]);
    626 	build(1, 0, n);
    627 	
    628 	int m;
    629 	scanf("%d", &m);
    630 	forn(_, m){
    631 		int t;
    632 		scanf("%d", &t);
    633 		if (t == 1){
    634 			int i;
    635 			scanf("%d", &i);
    636 			--i;
    637 			point tmp;
    638 			forn(j, k)
    639 				scanf("%d", &tmp[j]);
    640 			upd(1, 0, n, i, tmp);
    641 		}
    642 		else{
    643 			int l, r;
    644 			scanf("%d%d", &l, &r);
    645 			--l, --r;
    646 			forn(mask, 1 << k)
    647 				bst[mask] = INF;
    648 			get(1, 0, n, l, r + 1);
    649 			
    650 			int ans = 0;
    651 			forn(mask, 1 << k)
    652 				ans = max(ans, abs(bst[(1 << k) - 1 - mask] + bst[mask]));
    653 			printf("%d\n", ans);
    654 		}
    655 	}
    656 	return 0;
    657 }
    658 ```