1843.md (8650B)
1 Source: https://codeforces.com/blog/entry/117468 2 3 [1843A - Sasha and Array Coloring](/contest/1843/problem/A "Codeforces Round 881 (Div. 3)") 4 5 Idea: [Sokol080808](/profile/Sokol080808 "Master Sokol080808"), prepared: [molney](/profile/molney "Master molney") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 def solve(): 15 n = int(input()) 16 a = [int(x) for x in input().split()] 17 a.sort() 18 ans = 0 19 for i in range(n // 2): 20 ans += a[-i-1] - a[i] 21 print(ans) 22 23 24 t = int(input()) 25 for _ in range(t): 26 solve() 27 ``` 28 29 **Rate the problem** 30 31 * Didn't solve 32 * Good task 33 * Average task 34 * Bad task 35 36 [1843B - Long Long](/contest/1843/problem/B "Codeforces Round 881 (Div. 3)") 37 38 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [molney](/profile/molney "Master molney") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution** 45 46 ``` 47 T = int(input()) 48 for _ in range(T): 49 n = int(input()) 50 a = list(map(int, input().split())) 51 52 sum = 0 53 cnt = 0 54 open = False 55 for x in a: 56 sum += abs(x) 57 if x < 0 and not open: 58 open = True 59 cnt += 1 60 if x > 0: 61 open = False 62 63 print(sum, cnt) 64 ``` 65 66 **Rate the problem** 67 68 * Didn't solve 69 * Good task 70 * Average task 71 * Bad task 72 73 [1843C - Sum in Binary Tree](/contest/1843/problem/C "Codeforces Round 881 (Div. 3)") 74 75 Idea: [Sokol080808](/profile/Sokol080808 "Master Sokol080808"), prepared: [molney](/profile/molney "Master molney") 76 77 **Tutorial** 78 79 Tutorial is loading... 80 81 **Solution** 82 83 ``` 84 t = int(input()) 85 for _ in range(t): 86 n = int(input()) 87 s = 0 88 while n >= 1: 89 s += n 90 n //= 2 91 print(s) 92 ``` 93 94 **Rate the problem** 95 96 * Didn't solve 97 * Good task 98 * Average task 99 * Bad task 100 101 [1843D - Apple Tree](/contest/1843/problem/D "Codeforces Round 881 (Div. 3)") 102 103 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution** 110 111 ``` 112 #include <bits/stdc++.h> 113 using namespace std; 114 typedef long long ll; 115 116 vector<vector<int>> g; 117 vector<ll> cnt; 118 119 void dfs(int v, int p) { 120 if (g[v].size() == 1 && g[v][0] == p) { 121 cnt[v] = 1; 122 } else { 123 for (auto u : g[v]) { 124 if (u != p) { 125 dfs(u, v); 126 cnt[v] += cnt[u]; 127 } 128 } 129 } 130 } 131 132 void solve() { 133 int n, q; 134 cin >> n; 135 136 g.assign(n, vector<int>()); 137 138 for (int i = 0; i < n - 1; i++) { 139 int u, v; 140 cin >> u >> v; 141 u--; v--; 142 g[u].push_back(v); 143 g[v].push_back(u); 144 } 145 146 cnt.assign(n, 0); 147 dfs(0, -1); 148 149 cin >> q; 150 for (int i = 0; i < q; i++) { 151 int c, k; 152 cin >> c >> k; 153 c--; k--; 154 155 ll res = cnt[c] * cnt[k]; 156 cout << res << '\n'; 157 } 158 } 159 160 signed main() { 161 int tests; 162 cin >> tests; 163 while (tests--) { 164 solve(); 165 } 166 167 return 0; 168 } 169 ``` 170 171 **Rate the problem** 172 173 * Didn't solve 174 * Good task 175 * Average task 176 * Bad task 177 178 [1843E - Tracking Segments](/contest/1843/problem/E "Codeforces Round 881 (Div. 3)") 179 180 Idea: [meowcneil](/profile/meowcneil "Master meowcneil"), prepared: [meowcneil](/profile/meowcneil "Master meowcneil") 181 182 **Tutorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 def solve(): 190 n, m = map(int, input().split()) 191 segs = [] 192 for i in range(m): 193 l, r = map(int, input().split()) 194 l -= 1 195 segs.append([l, r]) 196 q = int(input()) 197 ord = [0] * q 198 for i in range(q): 199 ord[i] = int(input()) 200 ord[i] -= 1 201 l = 0 202 r = q + 1 203 while r - l > 1: 204 M = (l + r) // 2 205 cur = [0] * n 206 for i in range(M): 207 cur[ord[i]] = 1 208 pr = [0] * (n + 1) 209 for i in range(n): 210 pr[i+1] = pr[i] + cur[i] 211 ok = False 212 for i in segs: 213 if(pr[i[1]] - pr[i[0]] > (i[1] - i[0]) // 2): 214 ok = True 215 break 216 if ok: 217 r = M 218 else: 219 l = M 220 if r == q + 1: 221 r = -1 222 print(r) 223 224 tc = int(input()) 225 for T in range(tc): 226 solve() 227 ``` 228 229 **Rate the problem** 230 231 * Didn't solve 232 * Good task 233 * Average task 234 * Bad task 235 236 [1843F1 - Omsk Metro (simple version)](/contest/1843/problem/F1 "Codeforces Round 881 (Div. 3)") 237 238 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Sokol080808](/profile/Sokol080808 "Master Sokol080808") 239 240 **Tutorial** 241 242 Tutorial is loading... 243 244 **Solution** 245 246 ``` 247 class info: 248 mn_suf = 0 249 mx_suf = 0 250 mn_ans = 0 251 mx_ans = 0 252 253 def solve(): 254 n = int(input()) 255 256 start = info() 257 start.mx_suf = start.mx_ans = 1 258 259 st = [start] 260 for i in range(n): 261 com = input().split() 262 if (com[0] == '+'): 263 v = int(com[1]) - 1 264 x = int(com[2]) 265 266 pref = st[v] 267 cur = info() 268 269 cur.mn_suf = min(0, pref.mn_suf + x) 270 cur.mx_suf = max(0, pref.mx_suf + x) 271 cur.mn_ans = min(pref.mn_ans, cur.mn_suf) 272 cur.mx_ans = max(pref.mx_ans, cur.mx_suf) 273 274 st.append(cur) 275 else: 276 v = int(com[2]) - 1 277 x = int(com[3]) 278 279 if st[v].mn_ans <= x <= st[v].mx_ans: 280 print("Yes") 281 else: 282 print("No") 283 284 t = int(input()) 285 for testCase in range(t): 286 solve() 287 ``` 288 289 **Rate the problem** 290 291 * Didn't solve 292 * Good task 293 * Average task 294 * Bad task 295 296 [1843F2 - Omsk Metro (hard version)](/contest/1843/problem/F2 "Codeforces Round 881 (Div. 3)") 297 298 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), prepared: [Sokol080808](/profile/Sokol080808 "Master Sokol080808") 299 300 **Tutorial** 301 302 Tutorial is loading... 303 304 **Solution** 305 306 ``` 307 #include <bits/stdc++.h> 308 309 using namespace std; 310 311 typedef long long ll; 312 313 struct info { 314 int sum, minPrefL, maxPrefL, minPrefR, maxPrefR, minSeg, maxSeg; 315 316 info(int el = 0) { 317 sum = el; 318 minSeg = minPrefL = minPrefR = min(el, 0); 319 maxSeg = maxPrefL = maxPrefR = max(el, 0); 320 } 321 }; 322 323 struct question { 324 int u, v, x; 325 }; 326 327 info merge(info& a, info& b) { 328 info res; 329 res.sum = a.sum + b.sum; 330 res.minPrefL = min(a.minPrefL, a.sum + b.minPrefL); 331 res.maxPrefL = max(a.maxPrefL, a.sum + b.maxPrefL); 332 res.minPrefR = min(a.minPrefR + b.sum, b.minPrefR); 333 res.maxPrefR = max(a.maxPrefR + b.sum, b.maxPrefR); 334 res.minSeg = min({a.minSeg, b.minSeg, a.minPrefR + b.minPrefL}); 335 res.maxSeg = max({a.maxSeg, b.maxSeg, a.maxPrefR + b.maxPrefL}); 336 return res; 337 } 338 339 const int MAXN = 200100; 340 const int lg = 17; 341 342 int up[lg + 1][MAXN]; 343 info ans[lg + 1][MAXN]; 344 int d[MAXN]; 345 346 void solve() { 347 int n; 348 cin >> n; 349 350 for (int i = 0; i <= lg; i++) up[i][0] = 0; 351 ans[0][0] = info(1); 352 d[0] = 0; 353 354 int cur = 0; 355 for (int q = 0; q < n; q++) { 356 char c; 357 cin >> c; 358 if (c == '+') { 359 int v, x; 360 cin >> v >> x; 361 v--; 362 cur++; 363 364 d[cur] = d[v] + 1; 365 366 up[0][cur] = v; 367 for (int j = 0; j <= lg - 1; j++) up[j + 1][cur] = up[j][up[j][cur]]; 368 369 ans[0][cur] = info(x); 370 for (int j = 0; j <= lg - 1; j++) ans[j + 1][cur] = merge(ans[j][cur], ans[j][up[j][cur]]); 371 } else { 372 int u, v, x; 373 cin >> u >> v >> x; 374 u--; v--; 375 376 if (d[u] < d[v]) swap(u, v); 377 378 int dif = d[u] - d[v]; 379 info a, b; 380 for (int i = lg; i >= 0; i--) { 381 if ((dif >> i) & 1) { 382 a = merge(a, ans[i][u]); 383 u = up[i][u]; 384 } 385 } 386 387 if (u == v) { 388 a = merge(a, ans[0][u]); 389 } else { 390 for (int i = lg; i >= 0; i--) { 391 if (up[i][u] != up[i][v]) { 392 a = merge(a, ans[i][u]); 393 u = up[i][u]; 394 b = merge(b, ans[i][v]); 395 v = up[i][v]; 396 } 397 } 398 399 a = merge(a, ans[1][u]); 400 b = merge(b, ans[0][v]); 401 } 402 403 swap(b.minPrefL, b.minPrefR); 404 swap(b.maxPrefL, b.maxPrefR); 405 406 info res = merge(a, b); 407 if (res.minSeg <= x && x <= res.maxSeg) { 408 cout << "Yes\n"; 409 } else { 410 cout << "No\n"; 411 } 412 } 413 } 414 } 415 416 int main() { 417 int tests; 418 cin >> tests; 419 while (tests--) { 420 solve(); 421 } 422 } 423 ``` 424 425 **Rate the problem** 426 427 * Didn't solve 428 * Good task 429 * Average task 430 * Bad task