2126.md (10013B)
1 Source: https://codeforces.com/blog/entry/144845 2 3 [2126A - Only One Digit](/contest/2126/problem/A "Codeforces Round 1037 (Div. 3)") 4 5 Idea: [soullless](/profile/soullless "Master soullless") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 int main() { 17 int t; 18 cin >> t; 19 while(t--) { 20 int x; 21 cin >> x; 22 int mn = 9; 23 while(x > 0) { 24 mn = min(mn, x % 10); 25 x/=10; 26 } 27 cout << mn << endl; 28 } 29 } 30 ``` 31 32 [2126B - No Casino in the Mountains](/contest/2126/problem/B "Codeforces Round 1037 (Div. 3)") 33 34 Idea: [soullless](/profile/soullless "Master soullless") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution** 41 42 ``` 43 #include <bits/stdc++.h> 44 using namespace std; 45 int main() { 46 int t; 47 cin >> t; 48 while(t--) { 49 int n,k; 50 cin >> n >> k; 51 int a[n + 1]; 52 for(int i = 1;i <= n;i++) cin >> a[i]; 53 int ans = 0; 54 int cnt = 0; 55 for(int i = 1;i <= n;i++) { 56 if(a[i] == 1) { 57 ans+=(cnt + 1)/(k + 1); 58 cnt = 0; 59 continue; 60 } 61 else { 62 cnt++; 63 } 64 } 65 ans+=(cnt + 1)/(k + 1); 66 cout << ans << endl; 67 } 68 } 69 ``` 70 71 [2126C - I Will Definitely Make It](/contest/2126/problem/C "Codeforces Round 1037 (Div. 3)") 72 73 Idea: [soullless](/profile/soullless "Master soullless") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution** 80 81 ``` 82 #include <bits/stdc++.h> 83 using namespace std; 84 int main() { 85 int t; 86 cin >> t; 87 while(t--) { 88 int n,p; 89 cin >> n >> p; 90 int a[n + 1]; 91 for(int i = 1;i <= n;i++) cin >> a[i]; 92 int cur = a[p]; 93 int dist = a[p]; 94 sort(a + 1,a + n + 1); 95 bool ans = true; 96 for(int i = 1;i <= n;i++) { 97 if(a[i] < cur) continue; 98 if(a[i] — cur > dist) { 99 ans = false; 100 } 101 cur = a[i]; 102 } 103 if(ans) cout << "YES" << endl; 104 else cout << "NO" << endl; 105 } 106 } 107 ``` 108 109 [2126D - This Is the Last Time](/contest/2126/problem/D "Codeforces Round 1037 (Div. 3)") 110 111 Idea: [soullless](/profile/soullless "Master soullless") 112 113 **Tutorial** 114 115 Tutorial is loading... 116 117 **Solution** 118 119 ``` 120 #include <bits/stdc++.h> 121 using namespace std; 122 int main() { 123 int t; 124 cin >> t; 125 while(t--) { 126 int n,k; 127 cin >> n >> k; 128 pair <int,pair <int,int> > p[n + 1]; 129 for(int i = 1;i <= n;i++) cin >> p[i].first >> p[ыi].second.first >> p[i].second.second; 130 sort(p + 1,p + n + 1); 131 int cur = k; 132 for(int i = 1;i <= n;i++) { 133 if(p[i].first > cur) break; 134 cur = max(cur,p[i].second.second); 135 } 136 cout << cur << endl; 137 } 138 } 139 ``` 140 141 [2126E - G-C-D, Unlucky!](/contest/2126/problem/E "Codeforces Round 1037 (Div. 3)") 142 143 Idea: [Away_in_the_heavens](/profile/Away_in_the_heavens "Expert Away_in_the_heavens") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include <bits/stdc++.h> 153 using namespace std; 154 main() { 155 int t; 156 cin >> t; 157 while (t--) { 158 int n; 159 cin >> n; 160 long long a[n + 1]; 161 for (int i = 1; i <= n; i++) { 162 cin >> a[i]; 163 } 164 long long b[n + 1]; 165 for (int i = 1; i <= n; i++) { 166 cin >> b[i]; 167 } 168 long long ans[n + 1]; 169 for (int i = n; i >= 1; i--) { 170 ans[i] = lcm(a[i], b[i]); 171 } 172 bool ch = 1; 173 if(ans[1] != a[1]) ch = 0; 174 if(ans[n] != b[n]) ch = 0; 175 for (int i = 2; i <= n; i++) { 176 if (__gcd(a[i — 1], ans[i]) != a[i]) { 177 ch = 0; 178 } 179 } 180 for (int i = n — 1; i >= 1; i--) { 181 if (__gcd(b[i + 1], ans[i]) != b[i]) { 182 ch = 0; 183 } 184 } 185 if (ch) { 186 cout << "YES" << "\n"; 187 } else { 188 cout << "NO" << "\n"; 189 } 190 } 191 } 192 ``` 193 194 [2126F - 1-1-1, Free Tree!](/contest/2126/problem/F "Codeforces Round 1037 (Div. 3)") 195 196 Idea: [soullless](/profile/soullless "Master soullless") 197 198 **Tutorial** 199 200 Tutorial is loading... 201 202 **Solution** 203 204 ``` 205 #include <bits/stdc++.h> 206 using namespace std; 207 const int B = 2e5 + 100; 208 int n; 209 int col[B]; 210 long long costt = 0; 211 vector <pair <int,int> > reb[B]; 212 bool was[B]; 213 map <int,long long> cnt[B]; 214 int pred[B]; 215 long long zn[B]; 216 void dfs(int v) { 217 was[v] = true; 218 for(auto u:reb[v]) { 219 if(was[u.first]) { 220 pred[v] = u.first; 221 continue; 222 } 223 if(col[v] != col[u.first]) costt+=u.second; 224 dfs(u.first); 225 zn[u.first] = u.second; 226 cnt[v][col[u.first]]+=zn[u.first]; 227 } 228 } 229 void update(int v,int x) { 230 if(v != 1) { 231 cnt[pred[v]][col[v]]-=zn[v]; 232 if(col[pred[v]] == col[v]) costt+=zn[v]; 233 cnt[pred[v]][x]+=zn[v]; 234 if(col[pred[v]] == x) costt-=zn[v]; 235 } 236 else { 237 238 } 239 costt+=cnt[v][col[v]]; 240 costt-=cnt[v][x]; 241 col[v] = x; 242 } 243 void clr() { 244 for(int i = 1;i <= n;i++) { 245 reb[i].clear(); 246 was[i] = false; 247 cnt[i].clear(); 248 zn[i] = 0; 249 } 250 costt = 0; 251 } 252 int main() { 253 int t; 254 cin >> t; 255 while(t--) { 256 int q; 257 cin >> n >> q; 258 for(int i = 1; i <= n; i++) cin >> col[i]; 259 for(int i = 1; i < n; i++) { 260 int u, v, c; 261 cin >> u >> v >> c; 262 reb[v].push_back({u,c}); 263 reb[u].push_back({v,c}); 264 } 265 dfs(1); 266 while(q--) { 267 int pos,x; 268 cin >> pos >> x; 269 update(pos,x); 270 cout << costt << "\n"; 271 } 272 clr(); 273 } 274 } 275 ``` 276 277 [2126G1 - Big Wins! (easy version)](/contest/2126/problem/G1 "Codeforces Round 1037 (Div. 3)") 278 279 Idea: [soullless](/profile/soullless "Master soullless") 280 281 **Tutorial** 282 283 Tutorial is loading... 284 285 **Solution** 286 287 ``` 288 #include <bits/stdc++.h> 289 using namespace std; 290 const int B = 2e5 + 100; 291 292 int main() { 293 int t; 294 cin >> t; 295 while(t--) { 296 int n; 297 cin >> n; 298 int a[n + 1]; 299 for(int i = 1;i <= n;i++) cin >> a[i]; 300 int ans = 0; 301 for(int i = 1;i <= 100;i++) { 302 int b[n + 1] = {}; 303 for(int j = 1;j <= n;j++) { 304 if(a[j] >= i) b[j] = 1; 305 else b[j] = -1; 306 } 307 int pref[n + 1] = {}; 308 for(int j = 1; j <= n; j++) { 309 pref[j] = pref[j - 1] + b[j]; 310 } 311 int prefmn[n + 2] = {},suffmx[n + 1] = {}; 312 prefmn[0] = 0,suffmx[n] = pref[n]; 313 for(int j = 1; j <= n; j++) { 314 prefmn[j] = min(prefmn[j - 1],pref[j]); 315 } 316 for(int j = n - 1; j >= 1; j--) { 317 suffmx[j] = max(suffmx[j + 1],pref[j]); 318 } 319 for(int j = 1; j <= n; j++) { 320 if(prefmn[j - 1] <= pref[j] || pref[j - 1] <= suffmx[j]) { 321 ans = max(ans,i - a[j]); 322 } 323 } 324 } 325 cout << ans << endl; 326 } 327 } 328 ``` 329 330 [2126G2 - Big Wins! (hard version)](/contest/2126/problem/G2 "Codeforces Round 1037 (Div. 3)") 331 332 Idea: [soullless](/profile/soullless "Master soullless") 333 334 **Tutorial** 335 336 Tutorial is loading... 337 338 **Solution** 339 340 ``` 341 #include<bits/stdc++.h> 342 using namespace std; 343 int n; 344 int a[200005 + 2]; 345 array<int, 4> t[800005]; 346 array<int, 4> merge(array<int, 4>a, array<int, 4>b) { 347 int ans = max(a[0], b[0]); 348 int mxpref = max(a[1], a[3] + b[1]); 349 int mxsuff = max(b[2], a[2] + b[3]); 350 ans = max({ans, mxpref, mxsuff}); 351 int sum = a[3] + b[3]; 352 return {ans, mxpref, mxsuff, sum}; 353 } 354 void update(int v, int tl, int tr, int pos, int val) { 355 if (tl == tr) { 356 t[v] = {max(val, 0), max(val, 0), max(val, 0), val}; 357 } else { 358 int tm = (tl + tr) >> 1; 359 if (pos <= tm) { 360 update(v * 2, tl, tm, pos, val); 361 } else { 362 update(v * 2 + 1, tm + 1, tr, pos, val); 363 } 364 t[v] = merge(t[v * 2], t[v * 2 + 1]); 365 } 366 } 367 array<int, 4> get(int v, int tl, int tr, int l, int r) { 368 if (tl == l && tr == r) { 369 return t[v]; 370 } else if (l > r) { 371 return {0, 0, 0, 0}; 372 } else { 373 int tm = (tl + tr) >> 1; 374 return merge(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)); 375 } 376 } 377 int solve(int n, vector<int>A) { 378 int m = 0; 379 for (int i = 1; i <= n; i++) { 380 a[i] = A[i — 1]; 381 m = max(m, a[i]); 382 } 383 vector<int>ind[m + 1]; 384 for (int i = 1; i <= n; i++) { 385 ind[a[i]].push_back(i); 386 } 387 stack<int>s; 388 s.push(0); 389 a[0] = -INT_MAX; 390 int l[n + 1]; 391 for (int i = 1; i <= n; i++) { 392 while (a[s.top()] >= a[i]) { 393 s.pop(); 394 } 395 l[i] = s.top() + 1; 396 s.push(i); 397 } 398 a[n + 1] = -INT_MAX; 399 s.push(n + 1); 400 int r[n + 1]; 401 for (int i = n; i >= 1; i--) { 402 while (a[s.top()] >= a[i]) { 403 s.pop(); 404 } 405 r[i] = s.top() — 1; 406 s.push(i); 407 } 408 int med = 1; 409 for (int i = 1; i <= n; i++) { 410 update(1, 1, n, i, 1); 411 } 412 for (auto u : ind[1]) { 413 update(1, 1, n, u, -1); 414 } 415 int ans = 0; 416 for (int mn = 1; mn <= m; mn++) { 417 for (auto u : ind[mn]) { 418 int lg = l[u], rg = r[u]; 419 while (med < m && get(1, 1, n, lg, u — 1)[2] + get(1, 1, n, u + 1, rg)[1] + (a[u] < (med) ? -1 : 1) >= 0) { 420 med++; 421 for (auto u : ind[med]) { 422 update(1, 1, n, u, -1); 423 } 424 } 425 } 426 // cout << med << ' ' << mn << endl; 427 ans = max(ans, med — mn); 428 } 429 return ans; 430 } 431 int solveslow(int n, vector<int>A) { 432 for (int i = 1; i <= n; i++) { 433 a[i] = A[i — 1]; 434 } 435 int mx = 0; 436 for (int i = 1; i <= n; i++) { 437 vector<int>v; 438 for (int j = i; j <= n; j++) { 439 v.push_back(a[j]); 440 sort(v.begin(), v.end()); 441 mx = max(mx, v[v.size() / 2] — v[0]); 442 } 443 } 444 return mx; 445 } 446 int rnd() { 447 return (rand() + rand() * RAND_MAX); 448 } 449 main() { 450 ios_base::sync_with_stdio(false); 451 cin.tie(0); 452 int tt; 453 cin >> tt; 454 while(tt--) { 455 int n; 456 cin >> n; 457 vector<int>v; 458 for (int i = 1; i <= n; i++) { 459 int x; 460 cin >> x; 461 v.push_back(x); 462 } 463 cout << solve(n, v) << endl; 464 // cout << solveslow(n, v) << endl; 465 for(int i = 0;i <= n*4;i++) { 466 t[i][0] = 0; 467 t[i][1] = 0; 468 t[i][2] = 0; 469 t[i][3] = 0; 470 } 471 } 472 } 473 ```