1101.md (10129B)
1 Source: https://codeforces.com/blog/entry/64483 2 3 [1101A - Minimum Integer](/contest/1101/problem/A "Educational Codeforces Round 58 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (BledDest)** 10 11 ``` 12 q = int(input()) 13 for i in range(q): 14 l, r, d = map(int, input().split()) 15 if(d < l or d > r): 16 print(d) 17 else: 18 print((r // d) * d + d) 19 ``` 20 21 [1101B - Accordion](/contest/1101/problem/B "Educational Codeforces Round 58 (Rated for Div. 2)") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (Vovuh)** 28 29 ``` 30 #include <bits/stdc++.h> 31 32 using namespace std; 33 34 void rem(string &s, const string &c) { 35 auto pos = s.find(c); 36 if (pos == string::npos) { 37 cout << -1 << endl; 38 exit(0); 39 } 40 s.erase(0, pos + 1); 41 } 42 43 int main() { 44 #ifdef _DEBUG 45 freopen("input.txt", "r", stdin); 46 // freopen("output.txt", "w", stdout); 47 #endif 48 49 string s; 50 cin >> s; 51 52 rem(s, "["); 53 rem(s, ":"); 54 reverse(s.begin(), s.end()); 55 rem(s, "]"); 56 rem(s, ":"); 57 58 cout << count(s.begin(), s.end(), '|') + 4 << endl; 59 60 return 0; 61 } 62 ``` 63 64 [1101C - Division and Union](/contest/1101/problem/C "Educational Codeforces Round 58 (Rated for Div. 2)") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution (adedalic)** 71 72 ``` 73 #include<bits/stdc++.h> 74 75 using namespace std; 76 77 #define x first 78 #define y second 79 80 typedef pair<int, int> pt; 81 82 int n; 83 vector< pair<pt, int> > segs; 84 85 inline bool read() { 86 if(!(cin >> n)) 87 return false; 88 segs.resize(n); 89 for(int i = 0; i < n; i++) { 90 cin >> segs[i].x.x >> segs[i].x.y; 91 segs[i].y = i; 92 } 93 return true; 94 } 95 96 bool cmp(const pair<pt, int> &a, const pair<pt, int> &b) { 97 if(a.x.y != b.x.y) 98 return a.x.y < b.x.y; 99 if(a.x.x != b.x.x) 100 return a.x.x < b.x.x; 101 return a.y < b.y; 102 } 103 104 inline void solve() { 105 sort(segs.begin(), segs.end(), cmp); 106 107 int mn = segs[n - 1].x.x; 108 for(int i = n - 2; i >= 0; i--) { 109 if(segs[i].x.y < mn) { 110 vector<int> ts(n, 2); 111 for(int id = 0; id <= i; id++) 112 ts[segs[id].y] = 1; 113 114 for(int t : ts) 115 cout << t << ' '; 116 cout << '\n'; 117 118 return; 119 } 120 mn = min(mn, segs[i].x.x); 121 } 122 cout << -1 << '\n'; 123 } 124 125 int main() { 126 #ifdef _DEBUG 127 freopen("input.txt", "r", stdin); 128 int tt = clock(); 129 #endif 130 ios_base::sync_with_stdio(0); 131 cin.tie(0), cout.tie(0); 132 cout << fixed << setprecision(15); 133 134 int tc; 135 cin >> tc; 136 137 while(tc--) { 138 assert(read()); 139 solve(); 140 141 #ifdef _DEBUG 142 cerr << "TIME = " << clock() - tt << endl; 143 tt = clock(); 144 #endif 145 } 146 return 0; 147 } 148 ``` 149 150 [1101D - GCD Counting](/contest/1101/problem/D "Educational Codeforces Round 58 (Rated for Div. 2)") 151 152 **Tutorial** 153 154 Tutorial is loading... 155 156 **Solution (PikMike)** 157 158 ``` 159 #include <bits/stdc++.h> 160 161 using namespace std; 162 163 #define x first 164 #define y second 165 #define mp make_pair 166 #define pb push_back 167 #define sqr(a) ((a) * (a)) 168 #define sz(a) int(a.size()) 169 #define all(a) a.begin(), a.end() 170 #define forn(i, n) for(int i = 0; i < int(n); i++) 171 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 172 173 typedef long long li; 174 typedef long double ld; 175 typedef pair<int, int> pt; 176 177 template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) { 178 return out << "(" << a.x << ", " << a.y << ")"; 179 } 180 181 template <class A> ostream& operator << (ostream& out, const vector<A> &v) { 182 out << "["; 183 forn(i, sz(v)) { 184 if(i) out << ", "; 185 out << v[i]; 186 } 187 return out << "]"; 188 } 189 190 mt19937 rnd(time(NULL)); 191 192 const int INF = int(1e9); 193 const li INF64 = li(1e18); 194 const int MOD = INF + 7; 195 const ld EPS = 1e-9; 196 const ld PI = acos(-1.0); 197 198 const int N = 200 * 1000 + 13; 199 200 int n; 201 int a[N]; 202 vector<int> g[N]; 203 204 bool read () { 205 if (scanf("%d", &n) != 1) 206 return false; 207 forn(i, n) 208 g[i].clear(); 209 forn(i, n) 210 scanf("%d", &a[i]); 211 forn(i, n - 1){ 212 int x, y; 213 scanf("%d%d", &x, &y); 214 --x, --y; 215 g[x].pb(y); 216 g[y].pb(x); 217 } 218 return true; 219 } 220 221 vector<pt> dp[N]; 222 int ans; 223 224 void calc(int v, int p = -1){ 225 vector<pt> chd; 226 for (auto u : g[v]) if (u != p){ 227 calc(u, v); 228 for (auto it : dp[u]) 229 chd.pb(it); 230 } 231 232 sort(all(chd)); 233 forn(i, sz(chd)){ 234 int j = i - 1; 235 int mx1 = 0, mx2 = 0; 236 while (j + 1 < sz(chd) && chd[j + 1].x == chd[i].x){ 237 ++j; 238 if (chd[j].y >= mx1) 239 mx2 = mx1, mx1 = chd[j].y; 240 else if (chd[j].y > mx2) 241 mx2 = chd[j].y; 242 } 243 if (a[v] % chd[i].x == 0){ 244 ans = max(ans, mx1 + mx2 + 1); 245 dp[v].pb(mp(chd[i].x, mx1 + 1)); 246 while (a[v] % chd[i].x == 0) 247 a[v] /= chd[i].x; 248 } 249 else{ 250 ans = max(ans, mx1); 251 } 252 i = j; 253 } 254 255 for (int i = 2; i * i <= a[v]; ++i) if (a[v] % i == 0){ 256 dp[v].pb(mp(i, 1)); 257 ans = max(ans, 1); 258 while (a[v] % i == 0) 259 a[v] /= i; 260 } 261 262 if (a[v] > 1){ 263 dp[v].pb(mp(a[v], 1)); 264 ans = max(ans, 1); 265 } 266 } 267 268 void solve() { 269 forn(i, N) dp[i].clear(); 270 ans = 0; 271 calc(0); 272 printf("%d\n", ans); 273 } 274 275 int main() { 276 #ifdef _DEBUG 277 freopen("input.txt", "r", stdin); 278 // freopen("output.txt", "w", stdout); 279 280 int tt = clock(); 281 282 #endif 283 284 cerr.precision(15); 285 cout.precision(15); 286 cerr << fixed; 287 cout << fixed; 288 289 #ifdef _DEBUG 290 while(read()) { 291 #else 292 if (read()){ 293 #endif 294 solve(); 295 296 #ifdef _DEBUG 297 cerr << "TIME = " << clock() - tt << endl; 298 tt = clock(); 299 #endif 300 301 } 302 } 303 ``` 304 305 [1101E - Polycarp's New Job](/contest/1101/problem/E "Educational Codeforces Round 58 (Rated for Div. 2)") 306 307 **Tutorial** 308 309 Tutorial is loading... 310 311 **Solution (PikMike)** 312 313 ``` 314 #include <bits/stdc++.h> 315 316 #define forn(i, n) for (int i = 0; i < int(n); i++) 317 318 using namespace std; 319 320 int main() { 321 int n; 322 scanf("%d", &n); 323 int mxa = 0, mxb = 0; 324 static char buf[5]; 325 forn(i, n){ 326 int x, y; 327 scanf("%s%d%d", buf, &x, &y); 328 if (x < y) 329 swap(x, y); 330 if (buf[0] == '+'){ 331 mxa = max(mxa, x); 332 mxb = max(mxb, y); 333 } 334 else{ 335 puts(mxa <= x && mxb <= y ? "YES" : "NO"); 336 } 337 } 338 } 339 ``` 340 341 [1101F - Trucks and Cities](/contest/1101/problem/F "Educational Codeforces Round 58 (Rated for Div. 2)") 342 343 **Tutorial** 344 345 Tutorial is loading... 346 347 **Solution 1 (adedalic)** 348 349 ``` 350 #include<bits/stdc++.h> 351 using namespace std; 352 353 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 354 355 #define sz(a) int((a).size()) 356 #define all(a) (a).begin(), (a).end() 357 358 #define mp make_pair 359 #define pb push_back 360 361 #define x first 362 #define y second 363 364 typedef long long li; 365 typedef pair<int, int> pt; 366 367 const int INF = int(1e9); 368 const int N = 411; 369 370 int n, m; 371 int a[N]; 372 vector< pair<pt, pt> > qs; 373 374 inline bool read() { 375 if(!(cin >> n >> m)) 376 return false; 377 fore(i, 0, n) 378 cin >> a[i]; 379 qs.resize(m); 380 fore(i, 0, m) { 381 cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y; 382 qs[i].x.x--; qs[i].x.y--; 383 } 384 return true; 385 } 386 387 vector<int> ids[N]; 388 int d[N][N]; 389 390 inline void solve() { 391 fore(i, 0, m) 392 ids[qs[i].x.x].push_back(i); 393 li ans = -1; 394 395 fore(l, 0, n) { 396 fore(r, l, n) 397 d[0][r] = a[r] - a[l]; 398 399 fore(k, 1, n + 1) { 400 int opt = l; 401 fore(r, l, n) { 402 while(opt < r && max(d[k - 1][opt], a[r] - a[opt]) >= max(d[k - 1][opt + 1], a[r] - a[opt + 1])) 403 opt++; 404 405 d[k][r] = max(d[k - 1][opt], a[r] - a[opt]); 406 } 407 } 408 409 for(int id : ids[l]) 410 ans = max(ans, d[qs[id].y.y][qs[id].x.y] * 1ll * qs[id].y.x); 411 } 412 413 cout << ans << endl; 414 } 415 416 int main() { 417 #ifdef _DEBUG 418 freopen("input.txt", "r", stdin); 419 int tt = clock(); 420 #endif 421 ios_base::sync_with_stdio(0); 422 cin.tie(0), cout.tie(0); 423 cout << fixed << setprecision(15); 424 425 if(read()) { 426 solve(); 427 428 #ifdef _DEBUG 429 cerr << "TIME = " << clock() - tt << endl; 430 tt = clock(); 431 #endif 432 } 433 return 0; 434 } 435 ``` 436 437 **Solution 2 (adedalic)** 438 439 ``` 440 #include<bits/stdc++.h> 441 using namespace std; 442 443 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 444 445 #define sz(a) int((a).size()) 446 #define all(a) (a).begin(), (a).end() 447 448 #define mp make_pair 449 #define pb push_back 450 451 #define x first 452 #define y second 453 454 typedef long long li; 455 typedef pair<int, int> pt; 456 457 const int INF = int(1e9); 458 const li INF64 = li(1e18); 459 const int N = 411; 460 461 int n, m; 462 int a[N]; 463 vector< pair<pt, pt> > qs; 464 465 inline bool read() { 466 if(!(cin >> n >> m)) 467 return false; 468 fore(i, 0, n) 469 cin >> a[i]; 470 qs.resize(m); 471 fore(i, 0, m) { 472 cin >> qs[i].x.x >> qs[i].x.y >> qs[i].y.x >> qs[i].y.y; 473 qs[i].x.x--; qs[i].x.y--; 474 } 475 return true; 476 } 477 478 int getCnt(const pair<pt, pt> &q, li mx) { 479 li dist = mx / q.y.x; 480 481 int s = q.x.x, f = q.x.y; 482 int u = s, cnt = 0; 483 while(u < f) { 484 int v = u; 485 while(v < f && a[v + 1] - a[u] <= dist) 486 v++; 487 488 if(v == u) 489 return INF; 490 491 cnt++; 492 u = v; 493 } 494 return cnt - 1; 495 } 496 497 li upd(const pair<pt, pt> &q, li lf, li rg) { 498 if(getCnt(q, lf) <= q.y.y) 499 return lf; 500 501 while(rg - lf > 1) { 502 li mid = (lf + rg) >> 1; 503 (getCnt(q, mid) <= q.y.y ? rg : lf) = mid; 504 } 505 return rg; 506 } 507 508 inline unsigned int getHash(const vector<int> &vals) { 509 unsigned int hash = 0; 510 for(int v : vals) 511 hash = hash * 3 + v; 512 return hash; 513 } 514 515 inline void solve() { 516 auto seed = getHash(vector<int>(a, a + n)); 517 fore(i, 0, m) 518 seed = seed * 3 + getHash({qs[i].x.x, qs[i].x.y, qs[i].y.x, qs[i].y.y}); 519 mt19937 rnd(seed); 520 521 vector<int> ids(m, 0); 522 iota(all(ids), 0); 523 shuffle(all(ids), rnd); 524 525 li curv = 0; 526 for(int id : ids) 527 curv = upd(qs[id], curv, 2 * INF64); 528 cout << curv << endl; 529 } 530 531 int main() { 532 #ifdef _DEBUG 533 freopen("input.txt", "r", stdin); 534 int tt = clock(); 535 #endif 536 ios_base::sync_with_stdio(0); 537 cin.tie(0), cout.tie(0); 538 cout << fixed << setprecision(15); 539 540 if(read()) { 541 solve(); 542 543 #ifdef _DEBUG 544 cerr << "TIME = " << clock() - tt << endl; 545 tt = clock(); 546 #endif 547 } 548 return 0; 549 } 550 ``` 551 552 [1101G - (Zero XOR Subset)-less](/contest/1101/problem/G "Educational Codeforces Round 58 (Rated for Div. 2)") 553 554 **Tutorial** 555 556 Tutorial is loading... 557 558 **Solution (PikMike)** 559 560 ``` 561 #include <bits/stdc++.h> 562 563 #define forn(i, n) for (int i = 0; i < int(n); i++) 564 565 using namespace std; 566 567 const int N = 200 * 1000 + 13; 568 const int LOGN = 30; 569 570 int n; 571 int a[N], pr[N]; 572 int base[LOGN]; 573 574 void try_gauss(int v){ 575 for(int i = LOGN - 1; i >= 0; i--) 576 if (base[i] != -1 && (v & (1 << i))) 577 v ^= base[i]; 578 if (v == 0) 579 return; 580 for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){ 581 base[i] = v; 582 return; 583 } 584 } 585 586 int main() { 587 scanf("%d", &n); 588 forn(i, n) 589 scanf("%d", &a[i]); 590 memset(base, -1, sizeof(base)); 591 forn(i, n){ 592 pr[i + 1] = pr[i] ^ a[i]; 593 try_gauss(pr[i + 1]); 594 } 595 if (pr[n] == 0){ 596 puts("-1"); 597 return 0; 598 } 599 int siz = 0; 600 forn(i, LOGN) 601 siz += (base[i] != -1); 602 printf("%d\n", siz); 603 } 604 ```