2244.md (7675B)
1 Source: https://codeforces.com/blog/entry/155197 2 3 [2244A - Iskander and Drawings](/contest/2244/problem/A "Codeforces Round 1109 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using ll = long long; 15 using namespace std; 16 17 void I_love_feblokas(); 18 19 int32_t main() { 20 int32_t tc = 1; 21 cin >> tc; 22 while (tc-->0) { 23 I_love_feblokas(); 24 } 25 return 0; 26 } 27 28 void I_love_feblokas() { 29 int32_t ans = 0, cnt = 0; 30 int n; 31 cin >> n; 32 string s; 33 cin >> s; 34 for (auto &c : s) { 35 if (c == '*') { 36 cnt = 0; 37 } else { 38 cnt++; 39 } 40 ans = max(ans, (cnt + 1) / 2); 41 } 42 cout << ans << '\n'; 43 return; 44 } 45 ``` 46 47 [2244B - Nikita and Books](/contest/2244/problem/B "Codeforces Round 1109 (Div. 3)") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution** 54 55 ``` 56 #include <bits/stdc++.h> 57 58 using ll = long long; 59 using namespace std; 60 61 void I_love_feblokas(); 62 63 int32_t main() { 64 int32_t tc = 1; 65 cin >> tc; 66 while (tc-- > 0) { 67 I_love_feblokas(); 68 } 69 return 0; 70 } 71 72 void I_love_feblokas() { 73 int n; 74 cin >> n; 75 vector<ll> a(n); 76 for (auto &x : a) cin >> x; 77 ll cur = 0; 78 bool ok = true; 79 for (ll i = 0; i < n; ++i) { 80 cur += a[i]; 81 ll need = (i + 1) * (i + 2) / 2; 82 if (cur < need) { 83 ok = false; 84 } 85 } 86 if (ok) { 87 cout << "YES\n"; 88 } else { 89 cout << "NO\n"; 90 } 91 } 92 ``` 93 94 [2244C - Stepan and Permutation](/contest/2244/problem/C "Codeforces Round 1109 (Div. 3)") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Solution** 101 102 ``` 103 #include <bits/stdc++.h> 104 105 using ll = long long; 106 using namespace std; 107 108 void I_love_feblokas(); 109 110 int32_t main() { 111 int32_t tc = 1; 112 cin >> tc; 113 while (tc-- > 0) { 114 I_love_feblokas(); 115 } 116 return 0; 117 } 118 119 void I_love_feblokas() { 120 int n, x, y; 121 cin >> n >> x >> y; 122 vector<int> p(n); 123 for (auto &val : p) cin >> val; 124 125 int g = gcd(x, y); 126 bool ok = true; 127 128 for (int i = 0; i < n; ++i) { 129 if ((p[i] % g) != ((i + 1) % g)) { 130 ok = false; 131 break; 132 } 133 } 134 135 if (ok) { 136 cout << "YES\n"; 137 } else { 138 cout << "NO\n"; 139 } 140 } 141 ``` 142 143 [2244D - Yaroslav and Productivity](/contest/2244/problem/D "Codeforces Round 1109 (Div. 3)") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 ``` 152 #include <bits/stdc++.h> 153 154 using ll = long long; 155 using namespace std; 156 157 void I_love_feblokas(); 158 159 int32_t main() { 160 int32_t tc = 1; 161 cin >> tc; 162 while (tc-->0) { 163 I_love_feblokas(); 164 } 165 return 0; 166 } 167 168 void I_love_feblokas() { 169 int n, m; 170 ll ans = 0; 171 cin >> n >> m; 172 vector<ll> a(n), b(m); 173 for (auto &x : a) cin >> x; 174 for (auto &x : b) cin >> x; 175 b.push_back(0); 176 sort(b.begin(), b.end()); 177 vector<ll> pref(n + 1); 178 for (ll i = 0; i < n; ++i) { 179 pref[i + 1] = pref[i] + a[i]; 180 } 181 for (ll i = 1; i < b.size(); ++i) { 182 ans += abs(pref[b[i]] - pref[b[i - 1]]); 183 } 184 ans += pref[n] - pref[b.back()]; 185 cout << ans << '\n'; 186 return; 187 } 188 ``` 189 190 [2244E - Masha and the Garland](/contest/2244/problem/E "Codeforces Round 1109 (Div. 3)") 191 192 **Tutorial** 193 194 Tutorial is loading... 195 196 **Solution** 197 198 ``` 199 #include <bits/stdc++.h> 200 201 using namespace std; 202 203 void solve() { 204 int n, q; 205 cin >> n >> q; 206 string s; 207 cin >> s; 208 vector<int> pref(n, 0); 209 for (int i = 0; i < n — 1; ++i) { 210 pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0); 211 } 212 for (int i = 0; i < q; ++i) { 213 int l, r, k; 214 cin >> l >> r >> k; 215 if (l == r) { 216 cout << "YES\n"; 217 continue; 218 } 219 int c = pref[r — 1] — pref[l — 1]; 220 int needed = (c + 1) / 2; 221 if (needed <= k) cout << "YES\n"; 222 else cout << "NO\n"; 223 } 224 } 225 226 int main() { 227 int t; 228 cin >> t; 229 while (t--) solve(); 230 return 0; 231 } 232 ``` 233 234 [2244F - Anya Loves Trees!](/contest/2244/problem/F "Codeforces Round 1109 (Div. 3)") 235 236 **Tutorial** 237 238 Tutorial is loading... 239 240 **Solution** 241 242 ``` 243 #include <bits/stdc++.h> 244 245 using ll = long long; 246 using namespace std; 247 248 vector<vector<int>> g; 249 vector<int> leaf; 250 bool ok; 251 252 void I_love_feblokas(); 253 pair<int, int> dfs(int u, int p); 254 255 int32_t main() { 256 int32_t tc = 1; 257 cin >> tc; 258 while (tc-- > 0) { 259 I_love_feblokas(); 260 } 261 return 0; 262 } 263 264 pair<int, int> dfs(int u, int p) { 265 if (!ok) return {0, 0}; 266 if (leaf[u] != 0) { 267 for (int v : g[u]) { 268 if (v != p) { 269 ok = false; 270 return {0, 0}; 271 } 272 } 273 return {leaf[u], leaf[u]}; 274 } 275 vector<pair<int, int>> segs; 276 for (int v : g[u]) { 277 if (v != p) { 278 segs.push_back(dfs(v, u)); 279 if (!ok) return {0, 0}; 280 } 281 } 282 if (segs.empty()) { 283 ok = false; 284 return {0, 0}; 285 } 286 vector<pair<int, int>> sorted_segs = segs; 287 sort(sorted_segs.begin(), sorted_segs.end()); 288 for (size_t i = 0; i < sorted_segs.size() — 1; ++i) { 289 if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) { 290 ok = false; 291 return {0, 0}; 292 } 293 } 294 int start_pos = -1; 295 for (size_t i = 0; i < segs.size(); ++i) { 296 if (segs[i] == sorted_segs[0]) { 297 start_pos = i; 298 break; 299 } 300 } 301 if (start_pos == -1) { 302 ok = false; 303 return {0, 0}; 304 } 305 for (size_t i = 0; i < segs.size(); ++i) { 306 if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) { 307 ok = false; 308 return {0, 0}; 309 } 310 } 311 return {sorted_segs[0].first, sorted_segs.back().second}; 312 } 313 314 void I_love_feblokas() { 315 int n; 316 cin >> n; 317 g.assign(n + 1, vector<int>()); 318 leaf.assign(n + 1, 0); 319 ok = true; 320 for (int i = 2; i <= n; ++i) { 321 int p; 322 cin >> p; 323 g[p].push_back(i); 324 g[i].push_back(p); 325 } 326 int k = 0; 327 for (int i = 1; i <= n; ++i) { 328 cin >> leaf[i]; 329 k = max(k, leaf[i]); 330 } 331 if (n == 1) { 332 cout << "YES\n"; 333 return; 334 } 335 pair<int, int> res = dfs(1, -1); 336 if (ok && res.first == 1 && res.second == k) { 337 cout << "YES\n"; 338 } else { 339 cout << "NO\n"; 340 } 341 } 342 ``` 343 344 [2244G - Yura and Deadlines](/contest/2244/problem/G "Codeforces Round 1109 (Div. 3)") 345 346 **Tutorial** 347 348 Tutorial is loading... 349 350 **Solution** 351 352 ``` 353 #include <bits/stdc++.h> 354 355 using namespace std; 356 using ll = long long; 357 358 struct Fenwick { 359 int n; 360 vector<ll> t; 361 362 Fenwick(int n) : n(n), t(n + 1, 0ll) {} 363 364 int f(int x) { 365 return x & -x; 366 } 367 368 void upd(int pos, ll val) { 369 for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val); 370 } 371 372 ll get(int pos) { 373 ll ans = 0; 374 for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]); 375 return ans; 376 } 377 }; 378 379 void I_love_feblokas() { 380 int n; 381 cin >> n; 382 vector<ll> a(n + 1); 383 for (int i = 1; i <= n; ++i) { 384 cin >> a[i]; 385 } 386 Fenwick t(n); 387 vector<vector<pair<int, ll>>> ev(n + 1); 388 ll ans = 0; 389 for (int i = 1; i <= n; ++i) { 390 for (auto& ev : ev[i]) { 391 t.upd(ev.first, ev.second); 392 } 393 int lim = i - a[i] - 1; 394 ll mx = 0; 395 if (lim > 0) { 396 mx = t.get(min(n, lim)); 397 } 398 ll dp_i = a[i] + mx; 399 ans = max(ans, dp_i); 400 ll act = i + a[i] + 1; 401 if (act <= n) { 402 ev[act].push_back({i, dp_i}); 403 } 404 } 405 cout << ans << "\n"; 406 } 407 408 int main() { 409 int t; 410 cin >> t ; 411 while (t--) { 412 I_love_feblokas(); 413 } 414 return 0; 415 } 416 ```