2075.md (8557B)
1 Source: https://codeforces.com/blog/entry/140781 2 3 [2075A - To Zero](/contest/2075/problem/A "Educational Codeforces Round 176 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n, k = map(int, input().split()) 17 ans = 0 18 if n % 2 == 1: 19 n -= k 20 ans = 1 21 k -= 1 22 ans += (n + k - 1) // k 23 print(ans) 24 ``` 25 26 [2075B - Array Recoloring](/contest/2075/problem/B "Educational Codeforces Round 176 (Rated for Div. 2)") 27 28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (Neon)** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 int main() { 42 int t; 43 cin >> t; 44 while (t--) { 45 int n, k; 46 cin >> n >> k; 47 vector<int> a(n); 48 for (auto &x : a) cin >> x; 49 long long ans = 0; 50 if (k > 1) { 51 sort(a.begin(), a.end(), greater<int>()); 52 ans = accumulate(a.begin(), a.begin() + k + 1, 0LL); 53 } else { 54 int l = *max_element(a.begin(), a.end() - 1); 55 int r = *max_element(a.begin() + 1, a.end()); 56 ans = max(l + a.back(), r + a[0]); 57 } 58 cout << ans << '\n'; 59 } 60 } 61 ``` 62 63 [2075C - Two Colors](/contest/2075/problem/C "Educational Codeforces Round 176 (Rated for Div. 2)") 64 65 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution (awoo)** 72 73 ``` 74 from bisect import bisect_left 75 76 for _ in range(int(input())): 77 n, m = map(int, input().split()) 78 a = sorted(list(map(int, input().split()))) 79 ans = 0 80 for k in range(1, n): 81 x = m - bisect_left(a, k) 82 y = m - bisect_left(a, n - k) 83 ans += x * y - min(x, y) 84 print(ans) 85 ``` 86 87 [2075D - Equalization](/contest/2075/problem/D "Educational Codeforces Round 176 (Rated for Div. 2)") 88 89 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution (Neon)** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 using namespace std; 101 102 using li = long long; 103 104 const int B = 60; 105 const li INF = 1e18; 106 107 int main() { 108 ios::sync_with_stdio(false); cin.tie(0); 109 array<array<li, B>, B> dp; 110 for (int i = 0; i < B; ++i) { 111 for (int j = 0; j < B; ++j) { 112 dp[i][j] = INF; 113 } 114 } 115 dp[0][0] = 0; 116 for (int x = 0; x < B; ++x) { 117 for (int i = B - 1; i >= 0; --i) { 118 for (int j = B - 1; j >= 0; --j) { 119 if (dp[i][j] == INF) continue; 120 if (i + x < B) dp[i + x][j] = min(dp[i + x][j], dp[i][j] + (1LL << x)); 121 if (j + x < B) dp[i][j + x] = min(dp[i][j + x], dp[i][j] + (1LL << x)); 122 } 123 } 124 } 125 int t; 126 cin >> t; 127 while (t--) { 128 li x, y; 129 cin >> x >> y; 130 li ans = INF; 131 for (int i = 0; i < B; ++i) { 132 for (int j = 0; j < B; ++j) { 133 if ((x >> i) == (y >> j)) ans = min(ans, dp[i][j]); 134 } 135 } 136 cout << ans << '\n'; 137 } 138 } 139 ``` 140 141 [2075E - XOR Matrix](/contest/2075/problem/E "Educational Codeforces Round 176 (Rated for Div. 2)") 142 143 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution (BledDest)** 150 151 ``` 152 #include <bits/stdc++.h> 153 154 using namespace std; 155 156 const int MOD = 998244353; 157 const int K = 31; 158 159 int add(int x, int y) 160 { 161 x += y; 162 while(x >= MOD) x -= MOD; 163 while(x < 0) x += MOD; 164 return x; 165 } 166 167 int sub(int x, int y) 168 { 169 return add(x, -y); 170 } 171 172 int mul(int x, int y) 173 { 174 return (x * 1ll * y) % MOD; 175 } 176 177 int binpow(int x, int y) 178 { 179 int z = 1; 180 while(y) 181 { 182 if(y & 1) z = mul(z, x); 183 x = mul(x, x); 184 y >>= 1; 185 } 186 return z; 187 } 188 189 int dp[K][2][2][2]; 190 191 int choose2(int n) 192 { 193 return mul(n, mul(sub(n, 1), binpow(2, MOD - 2))); 194 } 195 196 void solve() 197 { 198 int n, m, A, B; 199 cin >> n >> m >> A >> B; 200 201 memset(dp, 0, sizeof dp); 202 dp[0][0][0][0] = 1; 203 for(int i = 0; i + 1 < K; i++) 204 for(int f1 = 0; f1 <= 1; f1++) 205 for(int f2 = 0; f2 <= 1; f2++) 206 for(int fx = 0; fx <= 1; fx++) 207 { 208 int d = dp[i][f1][f2][fx]; 209 if(!d) continue; 210 int j = K - 2 - i; 211 int curA = (A >> j) & 1; 212 int curB = (B >> j) & 1; 213 for(int bit_a = 0; bit_a <= 1; bit_a++) 214 for(int bit_b = 0; bit_b <= 1; bit_b++) 215 for(int bit_x = 0; bit_x <= 1; bit_x++) 216 { 217 if(f1 == 0 && bit_a == 1 && curA == 0) continue; 218 if(f2 == 0 && bit_b == 1 && curB == 0) continue; 219 if(fx == 0 && bit_x == 1 && (bit_a == 0 || bit_b == 0)) continue; 220 int nf1 = max(f1, bit_a ^ curA); 221 int nf2 = max(f2, bit_b ^ curB); 222 int nfx = max(fx, bit_x); 223 int& d2 = dp[i + 1][nf1][nf2][nfx]; 224 d2 = add(d2, d); 225 } 226 } 227 int pairs_of_pairs = 0; 228 for(int i = 0; i <= 1; i++) 229 for(int j = 0; j <= 1; j++) 230 pairs_of_pairs = add(pairs_of_pairs, dp[K - 1][i][j][1]); 231 232 int comb_a = sub(binpow(2, n), 2); 233 int comb_b = sub(binpow(2, m), 2); 234 235 int ans = mul(pairs_of_pairs, mul(comb_a, comb_b)); 236 ans = add(ans, mul(add(A, 1), add(B, 1))); 237 ans = add(ans, mul(add(A, 1), mul(comb_b, choose2(add(B, 1))))); 238 ans = add(ans, mul(add(B, 1), mul(comb_a, choose2(add(A, 1))))); 239 cout << ans << endl; 240 } 241 242 int main() 243 { 244 int t; 245 cin >> t; 246 for(int i = 0; i < t; i++) solve(); 247 } 248 ``` 249 250 [2075F - Beautiful Sequence Returns](/contest/2075/problem/F "Educational Codeforces Round 176 (Rated for Div. 2)") 251 252 Idea: [adedalic](/profile/adedalic "International Master adedalic") 253 254 **Tutorial** 255 256 Tutorial is loading... 257 258 **Solution (adedalic)** 259 260 ``` 261 #include<bits/stdc++.h> 262 263 using namespace std; 264 265 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 266 #define sz(a) int((a).size()) 267 268 typedef long long li; 269 typedef pair<int, int> pt; 270 271 const int INF = int(1e9); 272 const li INF64 = li(1e18); 273 274 vector<int> Tadd, Tmax; 275 276 int getmax(int v) { 277 return Tmax[v] + Tadd[v]; 278 } 279 void push(int v) { 280 Tadd[2 * v + 1] += Tadd[v]; 281 Tadd[2 * v + 2] += Tadd[v]; 282 Tadd[v] = 0; 283 } 284 void upd(int v) { 285 Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2)); 286 } 287 void addVal(int v, int l, int r, int lf, int rg, int val) { 288 if (l == lf && r == rg) { 289 Tadd[v] += val; 290 return; 291 } 292 push(v); 293 int mid = (l + r) >> 1; 294 if (lf < mid) 295 addVal(2 * v + 1, l, mid, lf, min(mid, rg), val); 296 if (rg > mid) 297 addVal(2 * v + 2, mid, r, max(lf, mid), rg, val); 298 upd(v); 299 } 300 301 int n; 302 vector<int> a; 303 304 inline bool read() { 305 if(!(cin >> n)) 306 return false; 307 a.resize(n); 308 fore (i, 0, n) 309 cin >> a[i]; 310 return true; 311 } 312 313 inline void solve() { 314 vector<int> ask(n, 0); 315 int mx = -1; 316 for (int i = n - 1; i >= 0; i--) { 317 if (a[i] > mx) { 318 ask[i] = 1; 319 mx = a[i]; 320 } 321 } 322 vector<int> left; 323 fore (i, 0, n) { 324 if (left.empty() || a[left.back()] > a[i]) 325 left.push_back(i); 326 } 327 328 vector<pt> seg(n); 329 fore (i, 0, n) { 330 int lf = upper_bound(left.begin(), left.end(), i, [&left](int v, int i) { 331 return a[v] > a[i]; 332 }) - left.begin(); 333 int rg = lower_bound(left.begin(), left.end(), i) - left.begin(); 334 seg[i] = {lf, rg}; 335 } 336 337 Tadd.assign(4 * n, 0); 338 Tmax.assign(4 * n, 0); 339 340 vector<int> ordToAdd(n); 341 iota(ordToAdd.begin(), ordToAdd.end(), 0); 342 sort(ordToAdd.begin(), ordToAdd.end(), [](int i, int j) { 343 return a[i] < a[j]; 344 }); 345 346 auto addToSeg = [&left, &seg](int id, int val) { 347 auto [lf, rg] = seg[id]; 348 if (lf < rg) 349 addVal(0, 0, sz(left), lf, rg, val); 350 }; 351 352 int ans = 0; 353 int pos = 0; 354 vector<int> added(n, 0); 355 for (int i = n - 1; i >= 0; i--) { 356 while (pos < n && a[ordToAdd[pos]] < a[i]) { 357 if (ordToAdd[pos] <= i) { 358 addToSeg(ordToAdd[pos], 1); 359 added[ordToAdd[pos]] = 1; 360 } 361 pos++; 362 } 363 if (ask[i]) { 364 auto [lf, rg] = seg[i]; 365 ans = max(ans, 1 + (lf < rg ? 1 + getmax(0) : 0)); 366 } 367 if (added[i]) { 368 addToSeg(i, -1); 369 added[i] = 0; 370 } 371 } 372 cout << ans << endl; 373 } 374 375 int main() { 376 #ifdef _DEBUG 377 freopen("input.txt", "r", stdin); 378 int tt = clock(); 379 #endif 380 ios_base::sync_with_stdio(false); 381 cin.tie(0), cout.tie(0); 382 cout << fixed << setprecision(15); 383 384 int t; cin >> t; 385 while(t--) { 386 (read()); 387 solve(); 388 389 #ifdef _DEBUG 390 cerr << "TIME = " << clock() - tt << endl; 391 tt = clock(); 392 #endif 393 } 394 return 0; 395 } 396 ```