1217.md (7992B)
1 Source: https://codeforces.com/blog/entry/69605 2 3 [1217A - Creating a Character](/contest/1217/problem/A "Educational Codeforces Round 72 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (adedalic)** 10 11 ``` 12 fun main() { 13 val t = readLine()!!.toInt() 14 for (ct in 1..t) { 15 val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() } 16 val minAddStr = maxOf(0, (exp + int - str + 2) / 2) 17 println(maxOf(exp - minAddStr + 1, 0)) 18 } 19 } 20 ``` 21 22 [1217B - Zmei Gorynich](/contest/1217/problem/B "Educational Codeforces Round 72 (Rated for Div. 2)") 23 24 Idea: [Roms](/profile/Roms "Master Roms") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (Roms)** 31 32 ``` 33 #include <bits/stdc++.h> 34 35 using namespace std; 36 37 const int N = 105; 38 39 int t; 40 int n, m; 41 int d[N], h[N]; 42 43 int main() { 44 cin >> t; 45 for(int tc = 0; tc < t; ++tc){ 46 cin >> n >> m; 47 int maxDH = -2e9; 48 for(int i = 0; i < n; ++i){ 49 cin >> d[i] >> h[i]; 50 maxDH = max(maxDH, d[i] - h[i]); 51 } 52 53 int res = 1; 54 int maxD = *max_element(d, d + n); 55 m -= maxD; 56 if(m > 0){ 57 if(maxDH <= 0) res = -1; 58 else res += (m + maxDH - 1) / maxDH; 59 } 60 cout << res << endl; 61 } 62 63 return 0; 64 } 65 ``` 66 67 [1217C - The Number Of Good Substrings](/contest/1217/problem/C "Educational Codeforces Round 72 (Rated for Div. 2)") 68 69 Idea: [Roms](/profile/Roms "Master Roms") 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 **Solution (Roms)** 76 77 ``` 78 #include <bits/stdc++.h> 79 80 using namespace std; 81 82 const int N = int(3e5) + 99; 83 84 int t; 85 string s; 86 int nxt[N]; 87 88 int main() { 89 cin >> t; 90 for(int tc = 0; tc < t; ++tc){ 91 cin >> s; 92 for(int i = 0; i < s.size(); ++i) 93 if(s[i] == '1') nxt[i] = i; 94 else nxt[i] = (i == 0? -1 : nxt[i - 1]); 95 int res = 0; 96 for(int r = 0; r < s.size(); ++r){ 97 int sum = 0; 98 for(int l = r; l >= 0 && r - l < 20; --l){ 99 if(s[l] == '0') continue; 100 sum += 1 << (r - l); 101 if(sum <= r - (l == 0? -1 : nxt[l - 1])) 102 ++res; 103 } 104 } 105 cout << res << endl; 106 } 107 108 return 0; 109 } 110 ``` 111 112 [1217D - Coloring Edges](/contest/1217/problem/D "Educational Codeforces Round 72 (Rated for Div. 2)") 113 114 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 115 116 **Tutorial** 117 118 Tutorial is loading... 119 120 **Solution (Roms)** 121 122 ``` 123 #include<bits/stdc++.h> 124 125 using namespace std; 126 127 const int N = int(1e6) + 55; 128 129 int n, m; 130 vector <pair<int, int> > g[N]; 131 int col[N]; 132 bool cyc; 133 int res[N]; 134 135 void dfs(int v){ 136 col[v] = 1; 137 for(auto p : g[v]){ 138 int to = p.first, id = p.second; 139 if(col[to] == 0){ 140 dfs(to); 141 res[id] = 1; 142 } 143 else if(col[to] == 2) 144 res[id] = 1; 145 else{ 146 res[id] = 2; 147 cyc = true; 148 } 149 } 150 col[v] = 2; 151 } 152 153 int main(){ 154 cin >> n >> m; 155 for(int i = 0; i < m; ++i){ 156 int u, v; 157 cin >> u >> v; 158 --u, --v; 159 g[u].push_back(make_pair(v, i)); 160 } 161 162 for(int i = 0; i < n; ++i) 163 if(col[i] == 0) 164 dfs(i); 165 166 cout << (cyc? 2 : 1) << endl; 167 for(int i = 0; i < m; ++i) cout << res[i] << ' '; 168 cout << endl; 169 return 0; 170 } 171 ``` 172 173 [1217E - Sum Queries?](/contest/1217/problem/E "Educational Codeforces Round 72 (Rated for Div. 2)") 174 175 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 176 177 **Tutorial** 178 179 Tutorial is loading... 180 181 **Solution (PikMike)** 182 183 ``` 184 #include <bits/stdc++.h> 185 186 #define forn(i, n) for (int i = 0; i < int(n); i++) 187 188 using namespace std; 189 190 const int N = 200 * 1000 + 13; 191 const int INF = 2e9; 192 const int LOGN = 9; 193 194 struct node{ 195 int best; 196 int mn[LOGN]; 197 node(){ 198 best = INF; 199 forn(i, LOGN) 200 mn[i] = INF; 201 } 202 int& operator [](int x){ 203 return mn[x]; 204 } 205 }; 206 207 int a[N]; 208 node t[4 * N]; 209 210 void upd(node &t, int val){ 211 int x = val; 212 forn(i, LOGN){ 213 if (x % 10 != 0) 214 t[i] = min(t[i], val); 215 x /= 10; 216 } 217 } 218 219 node merge(node &a, node &b){ 220 node c; 221 c.best = min(a.best, b.best); 222 forn(i, LOGN){ 223 c[i] = min(a[i], b[i]); 224 if (a[i] < INF && b[i] < INF) 225 c.best = min(c.best, a[i] + b[i]); 226 } 227 return c; 228 } 229 230 void build(int v, int l, int r){ 231 if (l == r - 1){ 232 t[v] = node(); 233 upd(t[v], a[l]); 234 return; 235 } 236 int m = (l + r) / 2; 237 build(v * 2, l, m); 238 build(v * 2 + 1, m, r); 239 t[v] = merge(t[v * 2], t[v * 2 + 1]); 240 } 241 242 void upd(int v, int l, int r, int pos, int val){ 243 if (l == r - 1){ 244 t[v] = node(); 245 upd(t[v], val); 246 return; 247 } 248 int m = (l + r) / 2; 249 if (pos < m) 250 upd(v * 2, l, m, pos, val); 251 else 252 upd(v * 2 + 1, m, r, pos, val); 253 t[v] = merge(t[v * 2], t[v * 2 + 1]); 254 } 255 256 node get(int v, int l, int r, int L, int R){ 257 if (l == L && r == R) 258 return t[v]; 259 int m = (l + r) / 2; 260 if (R <= m) 261 return get(v * 2, l, m, L, R); 262 if (L >= m) 263 return get(v * 2 + 1, m, r, L, R); 264 node ln = get(v * 2, l, m, L, m); 265 node rn = get(v * 2 + 1, m, r, m, R); 266 return merge(ln, rn); 267 } 268 269 int main() { 270 int n, m; 271 scanf("%d%d", &n, &m); 272 forn(i, n) 273 scanf("%d", &a[i]); 274 build(1, 0, n); 275 forn(i, m){ 276 int t, x, y; 277 scanf("%d%d%d", &t, &x, &y); 278 --x; 279 if (t == 1) 280 upd(1, 0, n, x, y); 281 else{ 282 node res = get(1, 0, n, x, y); 283 printf("%d\n", res.best == INF ? -1 : res.best); 284 } 285 } 286 return 0; 287 } 288 ``` 289 290 [1217F - Forced Online Queries Problem](/contest/1217/problem/F "Educational Codeforces Round 72 (Rated for Div. 2)") 291 292 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 293 294 **Tutorial** 295 296 Tutorial is loading... 297 298 **Solution (PikMike)** 299 300 ``` 301 #include <bits/stdc++.h> 302 303 #define forn(i, n) for (int i = 0; i < int(n); i++) 304 305 using namespace std; 306 307 const int BUF = 10 * 1000 * 1000 + 13; 308 const int N = 300 * 1000 + 13; 309 const int M = 300 * 1000 + 13; 310 const int P = 400; 311 312 struct query{ 313 int t, x, y; 314 int e0, e1; 315 }; 316 317 int n, m; 318 query q[M]; 319 320 int p[N], rk[N]; 321 322 int cnt; 323 int* where[BUF]; 324 int val[BUF]; 325 326 void rollback(){ 327 while (cnt > 0){ 328 *where[cnt - 1] = val[cnt - 1]; 329 --cnt; 330 } 331 } 332 333 int getp(int a){ 334 return (a == p[a] ? a : getp(p[a])); 335 } 336 337 void unite(int a, int b){ 338 a = getp(a), b = getp(b); 339 if (a == b) return; 340 if (rk[a] < rk[b]) swap(a, b); 341 where[cnt] = &rk[a]; 342 val[cnt++] = rk[a]; 343 where[cnt] = &p[b]; 344 val[cnt++] = p[b]; 345 assert(cnt <= BUF); 346 rk[a] += rk[b]; 347 p[b] = a; 348 } 349 350 int getpFast(int a){ 351 return (a == p[a] ? a : p[a] = getpFast(p[a])); 352 } 353 354 void uniteFast(int a, int b){ 355 a = getpFast(a), b = getpFast(b); 356 if (a == b) return; 357 if (rk[a] < rk[b]) swap(a, b); 358 rk[a] += rk[b]; 359 p[b] = a; 360 } 361 362 struct edge{ 363 int v, u; 364 }; 365 366 bool operator <(const edge &a, const edge &b){ 367 if (a.v != b.v) 368 return a.v < b.v; 369 return a.u < b.u; 370 } 371 372 edge edges[2 * M]; 373 map<edge, int> rev; 374 375 bool used[2 * M]; 376 bool state[2 * M]; 377 int ans[M]; 378 vector<int> cur; 379 380 void rebuild(int l){ 381 int r = min(m, l + P); 382 forn(i, n) p[i] = i, rk[i] = 1; 383 memset(used, 0, sizeof(used)); 384 memset(state, 0, sizeof(state)); 385 386 forn(i, l) if (q[i].t == 1){ 387 int e = (ans[i] ? q[i].e1 : q[i].e0); 388 used[e] = true; 389 state[e] ^= 1; 390 } 391 392 for (int i = l; i < r; ++i) if (q[i].t == 1) 393 used[q[i].e0] = used[q[i].e1] = false; 394 395 cur.clear(); 396 cnt = 0; 397 forn(i, l) if (q[i].t == 1){ 398 int e = (ans[i] ? q[i].e1 : q[i].e0); 399 if (used[e] && state[e]){ 400 state[e] = false; 401 uniteFast(edges[e].v, edges[e].u); 402 } 403 else if (!used[e] && state[e]){ 404 state[e] = false; 405 cur.push_back(e); 406 } 407 } 408 } 409 410 int get_edge(edge e){ 411 if (!rev.count(e)){ 412 int k = rev.size(); 413 edges[k] = e; 414 rev[e] = k; 415 } 416 return rev[e]; 417 } 418 419 int main(){ 420 scanf("%d%d", &n, &m); 421 forn(i, m){ 422 scanf("%d%d%d", &q[i].t, &q[i].x, &q[i].y); 423 --q[i].x, --q[i].y; 424 if (q[i].t == 1){ 425 edge e({q[i].x, q[i].y}); 426 if (e.v > e.u) swap(e.v, e.u); 427 q[i].e0 = get_edge(e); 428 e.v = (e.v + 1) % n, e.u = (e.u + 1) % n; 429 if (e.v > e.u) swap(e.v, e.u); 430 q[i].e1 = get_edge(e); 431 } 432 } 433 434 string res = ""; 435 ans[0] = 0; 436 forn(i, m){ 437 if (i % P == 0) 438 rebuild(i); 439 440 int x = (q[i].x + ans[i]) % n; 441 int y = (q[i].y + ans[i]) % n; 442 if (x > y) swap(x, y); 443 444 if (q[i].t == 1){ 445 rollback(); 446 int e = get_edge({x, y}); 447 auto it = find(cur.begin(), cur.end(), e); 448 if (it == cur.end()) 449 cur.push_back(e); 450 else 451 cur.erase(it); 452 ans[i + 1] = ans[i]; 453 } 454 else{ 455 for (auto e : cur) 456 unite(edges[e].v, edges[e].u); 457 bool rc = (getp(x) == getp(y)); 458 ans[i + 1] = rc; 459 res += ('0' + rc); 460 } 461 } 462 463 puts(res.c_str()); 464 return 0; 465 } 466 ```