1651.md (9951B)
1 Source: https://codeforces.com/blog/entry/100796 2 3 [1651A - Playoff](/contest/1651/problem/A "Educational Codeforces Round 124 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 print(2 ** n - 1) 18 ``` 19 20 [1651B - Prove Him Wrong](/contest/1651/problem/B "Educational Codeforces Round 124 (Rated for Div. 2)") 21 22 Idea: [adedalic](/profile/adedalic "International Master adedalic") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (awoo)** 29 30 ``` 31 for _ in range(int(input())): 32 n = int(input()) 33 if 3**(n-1) > 10**9: 34 print("NO") 35 else: 36 print("YES") 37 print(*[3**x for x in range(n)]) 38 ``` 39 40 [1651C - Fault-tolerant Network](/contest/1651/problem/C "Educational Codeforces Round 124 (Rated for Div. 2)") 41 42 Idea: [adedalic](/profile/adedalic "International Master adedalic") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution (adedalic)** 49 50 ``` 51 #include<bits/stdc++.h> 52 53 using namespace std; 54 55 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 56 57 typedef long long li; 58 59 const int INF = int(1e9); 60 61 int n; 62 vector<int> a, b; 63 64 inline bool read() { 65 if(!(cin >> n)) 66 return false; 67 a.resize(n); 68 fore (i, 0, n) 69 cin >> a[i]; 70 b.resize(n); 71 fore (i, 0, n) 72 cin >> b[i]; 73 return true; 74 } 75 76 int bestCandidate(const vector<int> &vals, int cur) { 77 int bst = INF + 10, pos = -1; 78 fore (i, 0, n) { 79 if (bst > abs(cur - vals[i])) { 80 bst = abs(cur - vals[i]); 81 pos = i; 82 } 83 } 84 return pos; 85 } 86 87 inline void solve() { 88 li bst = 10ll * INF; 89 90 vector<int> cds1 = {0, bestCandidate(b, a[0]), n - 1}; 91 vector<int> cds2 = {0, bestCandidate(b, a[n - 1]), n - 1}; 92 93 for (int var1 : cds1) { 94 for (int var2 : cds2) { 95 li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]); 96 97 if (var1 > 0 && var2 > 0) 98 ans += abs(b[0] - a[bestCandidate(a, b[0])]); 99 if (var1 < n - 1 && var2 < n - 1) 100 ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]); 101 102 bst = min(bst, ans); 103 } 104 } 105 cout << bst << endl; 106 } 107 108 int main() { 109 #ifdef _DEBUG 110 freopen("input.txt", "r", stdin); 111 #endif 112 ios_base::sync_with_stdio(false); 113 cin.tie(0), cout.tie(0); 114 115 int t; cin >> t; 116 while (t--) { 117 read(); 118 solve(); 119 } 120 return 0; 121 } 122 ``` 123 124 [1651D - Nearest Excluded Points](/contest/1651/problem/D "Educational Codeforces Round 124 (Rated for Div. 2)") 125 126 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 127 128 **Tutorial** 129 130 Tutorial is loading... 131 132 **Solution (vovuh)** 133 134 ``` 135 #include <bits/stdc++.h> 136 137 using namespace std; 138 139 int dx[] = {0, 0, -1, 1}; 140 int dy[] = {-1, 1, 0, 0}; 141 142 int main() { 143 #ifdef _DEBUG 144 freopen("input.txt", "r", stdin); 145 // freopen("output.txt", "w", stdout); 146 #endif 147 148 int n; 149 scanf("%d", &n); 150 vector<pair<int, int>> a(n); 151 for (auto &[x, y] : a) scanf("%d %d", &x, &y); 152 153 set<pair<int, int>> st(a.begin(), a.end()); 154 map<pair<int, int>, pair<int, int>> ans; 155 queue<pair<int, int>> q; 156 for (auto [x, y] : a) { 157 for (int i = 0; i < 4; ++i) { 158 int nx = x + dx[i], ny = y + dy[i]; 159 if (st.count({nx, ny})) { 160 continue; 161 } 162 ans[{x, y}] = {nx, ny}; 163 q.push({x, y}); 164 break; 165 } 166 } 167 168 while (!q.empty()) { 169 int x = q.front().first, y = q.front().second; 170 q.pop(); 171 for (int i = 0; i < 4; ++i) { 172 int nx = x + dx[i], ny = y + dy[i]; 173 if (!st.count({nx, ny}) || ans.count({nx, ny})) { 174 continue; 175 } 176 ans[{nx, ny}] = ans[{x, y}]; 177 q.push({nx, ny}); 178 } 179 } 180 181 for (auto [x, y] : a) { 182 auto it = ans[{x, y}]; 183 printf("%d %d\n", it.first, it.second); 184 } 185 186 return 0; 187 } 188 ``` 189 190 [1651E - Sum of Matchings](/contest/1651/problem/E "Educational Codeforces Round 124 (Rated for Div. 2)") 191 192 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution (BledDest)** 199 200 ``` 201 #include<bits/stdc++.h> 202 203 using namespace std; 204 205 const int N = 3043; 206 207 vector<int> g[2 * N]; 208 int n; 209 int used[2 * N]; 210 211 int choose2(int n) 212 { 213 return n * (n + 1) / 2; 214 } 215 216 int count_ways(int L, int R, const vector<int>& forbidden) 217 { 218 if(L > R) 219 { 220 int ml = *min_element(forbidden.begin(), forbidden.end()); 221 int mr = *max_element(forbidden.begin(), forbidden.end()); 222 return choose2(ml) + choose2(mr - ml - 1) + choose2(n - 1 - mr); 223 } 224 int minl = 0; 225 int maxl = L; 226 int minr = R; 227 int maxr = n - 1; 228 for(auto x : forbidden) 229 { 230 if(L <= x && x <= R) 231 return 0; 232 else if(x < L) minl = max(minl, x + 1); 233 else maxr = min(maxr, x - 1); 234 } 235 return (maxl - minl + 1) * (maxr - minr + 1); 236 } 237 238 vector<int> cur; 239 240 void dfs(int x) 241 { 242 if(used[x] == 1) return; 243 used[x] = 1; 244 cur.push_back(x); 245 for(auto y : g[x]) dfs(y); 246 } 247 248 long long calc(const vector<int>& cycle) 249 { 250 int m = cycle.size(); 251 int k = m / 2; 252 long long ans = 0; 253 for(int i = 0; i < m; i++) 254 { 255 int z = cycle[i]; 256 if(z >= n) z -= n; 257 ans += choose2(n) * 1ll * (choose2(z) + 0ll + choose2(n - z - 1)); 258 int l = n - 1, r = 0, L = n - 1, R = 0; 259 int pl = i, pr = i; 260 for(int j = 0; j < k; j++) 261 { 262 for(auto x : vector<int>({cycle[pl], cycle[pr]})) 263 { 264 if(x < n) 265 { 266 l = min(l, x); 267 r = max(r, x); 268 } 269 else 270 { 271 L = min(L, x - n); 272 R = max(R, x - n); 273 } 274 } 275 vector<int> f, F; 276 pl--; 277 if(pl < 0) pl += m; 278 pr++; 279 if(pr >= m) pr -= m; 280 for(auto x : vector<int>({cycle[pl], cycle[pr]})) 281 { 282 if(x < n) f.push_back(x); 283 else F.push_back(x - n); 284 } 285 long long add = count_ways(l, r, f) * 1ll * count_ways(L, R, F); 286 ans += add; 287 } 288 } 289 return ans; 290 } 291 292 int main() 293 { 294 cin >> n; 295 for(int i = 0; i < 2 * n; i++) 296 { 297 int x, y; 298 cin >> x >> y; 299 --x; 300 --y; 301 g[x].push_back(y); 302 g[y].push_back(x); 303 } 304 long long ans = n * 1ll * choose2(n) * 1ll * choose2(n) * 2ll; 305 for(int i = 0; i < n; i++) 306 { 307 if(used[i]) continue; 308 dfs(i); 309 vector<int> cycle = cur; 310 ans -= calc(cycle); 311 cur = vector<int>(); 312 } 313 cout << ans / 2 << endl; 314 } 315 ``` 316 317 [1651F - Tower Defense](/contest/1651/problem/F "Educational Codeforces Round 124 (Rated for Div. 2)") 318 319 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 320 321 **Tutorial** 322 323 Tutorial is loading... 324 325 **Solution (awoo)** 326 327 ``` 328 #include <bits/stdc++.h> 329 330 #define forn(i, n) for (int i = 0; i < int(n); i++) 331 332 using namespace std; 333 334 struct node{ 335 node *l, *r; 336 long long sumc, sumr; 337 node() : l(NULL), r(NULL), sumc(0), sumr(0) {} 338 node(node* l, node* r, long long sumc, long long sumr) : l(l), r(r), sumc(sumc), sumr(sumr) {} 339 }; 340 341 node* build(int l, int r, vector<int> &c){ 342 if (l == r - 1) 343 return new node(NULL, NULL, c[l], 0); 344 int m = (l + r) / 2; 345 node* nw = new node(); 346 nw->l = build(l, m, c); 347 nw->r = build(m, r, c); 348 nw->sumc = nw->l->sumc + nw->r->sumc; 349 return nw; 350 } 351 352 node* upd(node* v, int l, int r, int pos, int val){ 353 if (l == r - 1) 354 return new node(NULL, NULL, 0, val); 355 int m = (l + r) / 2; 356 node* nw = new node(v->l, v->r, 0, 0); 357 if (pos < m) 358 nw->l = upd(v->l, l, m, pos, val); 359 else 360 nw->r = upd(v->r, m, r, pos, val); 361 nw->sumc = nw->l->sumc + nw->r->sumc; 362 nw->sumr = nw->l->sumr + nw->r->sumr; 363 return nw; 364 } 365 366 long long getsum(node *v, int mult){ 367 return v->sumc + v->sumr * mult; 368 } 369 370 int trav(node *v, int l, int r, int L, int R, long long &lft, int mult){ 371 if (L >= R){ 372 return 0; 373 } 374 if (l == L && r == R && lft - getsum(v, mult) >= 0){ 375 lft -= getsum(v, mult); 376 return r - l; 377 } 378 if (l == r - 1){ 379 return 0; 380 } 381 int m = (l + r) / 2; 382 int cnt = trav(v->l, l, m, L, min(m, R), lft, mult); 383 if (cnt == max(0, min(m, R) - L)) 384 cnt += trav(v->r, m, r, max(m, L), R, lft, mult); 385 return cnt; 386 } 387 388 struct seg{ 389 int l, r, lst, cur; 390 }; 391 392 int main() { 393 int n; 394 scanf("%d", &n); 395 vector<int> c(n), r(n); 396 forn(i, n) scanf("%d%d", &c[i], &r[i]); 397 398 vector<int> ord(n); 399 iota(ord.begin(), ord.end(), 0); 400 sort(ord.begin(), ord.end(), [&](int x, int y){ 401 return c[x] / r[x] > c[y] / r[y]; 402 }); 403 vector<int> vals; 404 for (int i : ord) vals.push_back(c[i] / r[i]); 405 406 vector<node*> root(1, build(0, n, c)); 407 for (int i : ord) 408 root.push_back(upd(root.back(), 0, n, i, r[i])); 409 410 vector<seg> st; 411 for (int i = n - 1; i >= 0; --i) 412 st.push_back({i, i + 1, 0, c[i]}); 413 414 long long ans = 0; 415 int q; 416 scanf("%d", &q); 417 forn(_, q){ 418 int t; 419 long long h; 420 scanf("%d%lld", &t, &h); 421 while (!st.empty()){ 422 auto it = st.back(); 423 st.pop_back(); 424 if (it.r - it.l == 1){ 425 it.cur = min((long long)c[it.l], it.cur + (t - it.lst) * 1ll * r[it.l]); 426 if (it.cur <= h){ 427 h -= it.cur; 428 } 429 else{ 430 st.push_back({it.l, it.r, t, int(it.cur - h)}); 431 h = 0; 432 } 433 } 434 else{ 435 int mx = vals.rend() - lower_bound(vals.rbegin(), vals.rend(), t - it.lst); 436 int res = it.l + trav(root[mx], 0, n, it.l, it.r, h, t - it.lst); 437 assert(res <= it.r); 438 if (res != it.r){ 439 if (it.r - res > 1) 440 st.push_back({res + 1, it.r, it.lst, 0}); 441 int nw = min((long long)c[res], r[res] * 1ll * (t - it.lst)); 442 assert(nw - h > 0); 443 st.push_back({res, res + 1, t, int(nw - h)}); 444 h = 0; 445 } 446 } 447 if (h == 0){ 448 break; 449 } 450 } 451 if (st.empty()){ 452 st.push_back({0, n, t, 0}); 453 } 454 else if (st.back().l != 0){ 455 st.push_back({0, st.back().l, t, 0}); 456 } 457 ans += h; 458 } 459 460 printf("%lld\n", ans); 461 return 0; 462 } 463 ```