1059.md (8673B)
1 Source: https://codeforces.com/blog/entry/62238 2 3 [1059A - Cashier](/contest/1059/problem/A "Codeforces Round 514 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 const int maxn = 1e5 + 5; 17 18 int n, L, a; 19 int t[maxn], l[maxn]; 20 21 int main(){ 22 scanf("%d%d%d", &n, &L, &a); 23 for(int i = 0; i < n; i++){ 24 scanf("%d%d", &t[i], &l[i]); 25 } 26 int start = 0; 27 int ans = 0; 28 for(int i = 0; i < n; i++){ 29 ans += (t[i] - start)/a; 30 start = t[i] + l[i]; 31 } 32 ans += (L - start)/a; 33 printf("%d", ans); 34 return 0; 35 } 36 ``` 37 38 [1059B - Forgery](/contest/1059/problem/B "Codeforces Round 514 (Div. 2)") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Code** 45 46 ``` 47 #include<bits/stdc++.h> 48 49 using namespace std; 50 51 const int maxn = (int)1e3 + 3; 52 53 int n, m; 54 char a[maxn][maxn]; 55 bool can[maxn][maxn]; 56 vector<int> must_have[maxn][maxn]; 57 58 inline bool inside(int x, int y){ 59 return x >= 0 && y >= 0 && x < n && y < m; 60 } 61 62 int main(){ 63 scanf("%d%d", &n, &m); 64 for(int i = 0; i < n; i++) 65 for(int j = 0; j < m; j++) 66 can[i][j] = true; 67 for(int i = 0; i < n; i++) 68 for(int j = 0; j < m; j++){ 69 do{ 70 a[i][j] = getc(stdin); 71 }while(a[i][j] != '.' && a[i][j] != '#'); 72 for(int dx = -1; dx <= 1; dx++) 73 for(int dy = -1; dy <= 1; dy++){ 74 if(abs(dx) + abs(dy) == 0 || !inside(i + dx, j + dy))continue; 75 if(a[i][j] == '.')can[i + dx][j + dy] = false; 76 else if (i + dx != 0 && j + dy != 0 && i + dx != n - 1 && j + dy != m - 1)must_have[i][j].push_back((i + dx) * m + j + dy); 77 } 78 } 79 for(int i = 0; i < n; i++) 80 for(int j = 0; j < m; j++){ 81 bool good = false; 82 if(a[i][j] == '.')continue; 83 for(int cand : must_have[i][j]){ 84 int x = cand/m, y = cand%m; 85 good |= can[x][y]; 86 } 87 if(!good){printf("NO"); return 0;} 88 } 89 printf("YES"); 90 return 0; 91 } 92 ``` 93 94 [1059C - Sequence Transformation](/contest/1059/problem/C "Codeforces Round 514 (Div. 2)") 95 96 **Tutorial** 97 98 Tutorial is loading... 99 100 **Code** 101 102 ``` 103 #include <bits/stdc++.h> 104 105 using namespace std; 106 107 const int maxn = 1e6 + 6; 108 109 int seq[maxn]; 110 int ans[maxn]; 111 int ptr = 0; 112 113 void solve(int n, int mul){ 114 if(n == 1){ans[ptr++] = mul; return;} 115 if(n == 2){ans[ptr++] = mul; ans[ptr++] = mul * 2; return;} 116 if(n == 3){ans[ptr++] = mul; ans[ptr++] = mul; ans[ptr++] = mul * 3; return;} 117 for(int i = 0; i < n; i++)if(seq[i]&1)ans[ptr++] = mul; 118 for(int i = 0; i < n/2; i++)seq[i] = seq[2*i + 1]/2; 119 solve(n/2, mul * 2); 120 } 121 122 int main(){ 123 int n; 124 scanf("%d", &n); 125 for(int i = 0; i < n; i++)seq[i] = i + 1; 126 solve(n, 1); 127 for(int i = 0; i < n; i++)printf("%d ", ans[i]); 128 return 0; 129 } 130 ``` 131 132 [1059D - Nature Reserve](/contest/1059/problem/D "Codeforces Round 514 (Div. 2)") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Code** 139 140 ``` 141 #include<bits/stdc++.h> 142 143 using namespace std; 144 145 typedef long double dbl; 146 147 const dbl eps = 1e-9; 148 149 inline bool gt(const dbl & x, const dbl & y){ 150 return x > y + eps; 151 } 152 153 inline bool lt(const dbl & x, const dbl & y){ 154 return y > x + eps; 155 } 156 157 inline dbl safe_sqrt(const dbl & D){ 158 return D < 0 ? 0 : sqrt(D); 159 } 160 161 struct pt{ 162 dbl x, y; 163 pt(){} 164 pt(dbl a, dbl b):x(a), y(b){} 165 }; 166 167 const int N = 1e5 + 5; 168 const int STEPS = 150; 169 170 int n; 171 pt p[N]; 172 173 inline bool can(dbl R){ 174 dbl l = -1e16 - 1, r = 1e16 + 1; 175 for(int i = 0; i < n; i++){ 176 dbl b = -2 * p[i].x; 177 dbl c = p[i].x * p[i].x + p[i].y * p[i].y - 2 * p[i].y * R; 178 dbl D = b * b - 4 * c; 179 if(lt(D, 0)) 180 return false; 181 D = safe_sqrt(D); 182 dbl x1 = p[i].x - D/2, x2 = p[i].x + D/2; 183 l = max(l, x1); 184 r = min(r, x2); 185 } 186 return !gt(l, r); 187 } 188 189 int main(){ 190 ios_base::sync_with_stdio(false); 191 cin.tie(0); 192 cin >> n; 193 bool has_positive = false, has_negative = false; 194 for(int i = 0; i < n; i++){ 195 int x, y; 196 cin >> x >> y; 197 p[i] = pt(x, y); 198 if(y > 0)has_positive = true; 199 else has_negative = true; 200 } 201 if(has_positive && has_negative){ 202 cout << -1 << endl; 203 return 0; 204 } 205 if(has_negative){ 206 for(int i = 0; i < n; i++) 207 p[i].y = -p[i].y; 208 } 209 dbl L = 0, R = 1e16; 210 std::function<dbl(dbl, dbl)> get_mid; 211 if(can(1)){ 212 R = 1; 213 get_mid = [](dbl l, dbl r){return (l + r)/2.0;}; 214 } 215 else{ 216 L = 1; 217 get_mid = [](dbl l, dbl r){return sqrt(l * r);}; 218 } 219 for(int step = 0; step < STEPS; step++){ 220 dbl mid = get_mid(L, R); 221 if(can(mid)) 222 R = mid; 223 else 224 L = mid; 225 } 226 cout.precision(16); 227 cout << fixed << get_mid(L, R) << endl; 228 } 229 ``` 230 231 [1059E - Split the Tree](/contest/1059/problem/E "Codeforces Round 514 (Div. 2)") 232 233 **Tutorial** 234 235 Tutorial is loading... 236 237 **Code (first solution)** 238 239 ``` 240 #include<bits/stdc++.h> 241 242 using namespace std; 243 244 typedef long long ll; 245 246 const int maxn = 1e5 + 5; 247 const int lg = 20; 248 const ll inf = 1e18; 249 250 int n, L; 251 ll S; 252 ll t[4 * maxn]; 253 ll t_add[4 * maxn]; 254 int cid = 0; 255 int w[maxn]; 256 vector<int> down[maxn]; 257 ll sum[maxn]; 258 int up[maxn]; 259 int p[maxn][lg]; 260 ll dp[maxn]; 261 int id[maxn], rb[maxn]; 262 ll dp_sum[maxn]; 263 vector<int> rm[maxn]; 264 265 inline ll get_sum(int v){ 266 return v == -1 ? 0 : sum[v]; 267 } 268 269 void preprocess(int v, int pr = -1){ 270 sum[v] = get_sum(pr) + w[v]; 271 p[v][0] = pr; 272 up[v] = v; 273 id[v] = rb[v] = cid++; 274 for(int i = 1; i < lg; i++) 275 p[v][i] = p[v][i - 1] == -1 ? -1 : p[p[v][i - 1]][i - 1]; 276 int dist = L - 1; 277 for(int i = lg - 1; i >= 0; i--){ 278 if(p[up[v]][i] == -1 || (1<<i) > dist)continue; 279 if(get_sum(v) - get_sum(p[up[v]][i]) + w[p[up[v]][i]] <= S){ 280 dist -= 1<<i; 281 up[v] = p[up[v]][i]; 282 } 283 } 284 rm[up[v]].push_back(v); 285 for(int u : down[v]){ 286 preprocess(u, v); 287 rb[v] = max(rb[v], rb[u]); 288 } 289 } 290 291 inline void push(int v){ 292 t[2*v] += t_add[v]; 293 t[2*v + 1] += t_add[v]; 294 t_add[2*v] += t_add[v]; 295 t_add[2*v + 1] += t_add[v]; 296 t_add[v] = 0; 297 } 298 299 void build_tree(int v, int l, int r){ 300 t[v] = inf; 301 if(l == r) 302 return; 303 int mid = (l + r)/2; 304 build_tree(2*v, l, mid); 305 build_tree(2*v + 1, mid + 1, r); 306 } 307 308 ll get_tree(int v, int l, int r, int ul, int ur){ 309 if(ul > ur) 310 return inf; 311 if(l == ul && r == ur) 312 return t[v]; 313 push(v); 314 int mid = (l + r)/2; 315 return min(get_tree(2*v, l, mid, ul, min(ur, mid)), get_tree(2*v + 1, mid + 1, r, max(ul, mid + 1), ur)); 316 } 317 318 void set_tree(int v, int l, int r, int pos, ll val){ 319 if(l == r){ 320 t[v] = val; 321 return; 322 } 323 push(v); 324 int mid = (l + r)/2; 325 if(pos <= mid) 326 set_tree(2*v, l, mid, pos, val); 327 else 328 set_tree(2*v + 1, mid + 1, r, pos, val); 329 t[v] = min(t[2*v], t[2*v + 1]); 330 } 331 332 void add_tree(int v, int l, int r, int ul, int ur, ll val){ 333 if(ul > ur)return; 334 if(l == ul && r == ur){ 335 t[v] += val; 336 t_add[v] += val; 337 return; 338 } 339 push(v); 340 int mid = (l + r)/2; 341 add_tree(2*v, l, mid, ul, min(ur, mid), val); 342 add_tree(2*v + 1, mid + 1, r, max(ul, mid + 1), ur, val); 343 t[v] = min(t[2*v], t[2*v + 1]); 344 } 345 346 inline void upd(int v){ 347 dp[v] = 1 + get_tree(1, 0, n - 1, id[v], rb[v]); 348 } 349 350 inline void add(int v){ 351 set_tree(1, 0, n - 1, id[v], 0); 352 add_tree(1, 0, n - 1, id[v], rb[v], dp_sum[v] - dp[v]); 353 } 354 355 inline void remove(int v){ 356 set_tree(1, 0, n - 1, id[v], inf); 357 } 358 359 void solve(int v){ 360 for(int u : down[v]){ 361 solve(u); 362 dp_sum[v] += dp[u]; 363 } 364 add(v); 365 dp[v] = maxn; 366 upd(v); 367 add_tree(1, 0, n - 1, id[v], rb[v], -dp[v]); 368 for(int u : rm[v]) 369 remove(u); 370 } 371 372 int main(){ 373 scanf("%d%d%lld", &n, &L, &S); 374 for(int i = 0; i < n; i++){ 375 scanf("%d", &w[i]); 376 if(w[i] > S){printf("-1"); return 0;} 377 } 378 for(int i = 1; i < n; i++){ 379 int j; 380 scanf("%d", &j); 381 down[--j].push_back(i); 382 } 383 preprocess(0); 384 build_tree(1, 0, n - 1); 385 solve(0); 386 printf("%lld", dp[0]); 387 } 388 ``` 389 390 **Code (second solution)** 391 392 ``` 393 #include<bits/stdc++.h> 394 395 using namespace std; 396 397 typedef long long ll; 398 399 const int maxn = 1e5 + 5; 400 const int lg = 20; 401 const ll inf = 1e18; 402 403 int n, L; 404 ll S; 405 int w[maxn]; 406 vector<int> down[maxn]; 407 ll sum[maxn]; 408 int up[maxn]; 409 int h[maxn]; 410 int p[maxn][lg]; 411 int path[maxn]; 412 413 inline ll get_sum(int v){ 414 return v == -1 ? 0 : sum[v]; 415 } 416 417 void preprocess(int v, int pr = -1){ 418 sum[v] = get_sum(pr) + w[v]; 419 p[v][0] = pr; 420 h[v] = pr == -1 ? 0 : (1 + h[pr]); 421 up[v] = v; 422 for(int i = 1; i < lg; i++) 423 p[v][i] = p[v][i - 1] == -1 ? -1 : p[p[v][i - 1]][i - 1]; 424 int dist = L - 1; 425 for(int i = lg - 1; i >= 0; i--){ 426 if(p[up[v]][i] == -1 || (1<<i) > dist)continue; 427 if(get_sum(v) - get_sum(p[up[v]][i]) + w[p[up[v]][i]] <= S){ 428 dist -= 1<<i; 429 up[v] = p[up[v]][i]; 430 } 431 } 432 for(int u : down[v]){ 433 preprocess(u, v); 434 } 435 } 436 437 int solve(int v){ 438 int ans = 0; 439 int best = -1; 440 for(int u : down[v]){ 441 ans += solve(u); 442 if(path[u] == u)continue; 443 if(best == -1 || h[best] > h[path[u]]) 444 best = path[u]; 445 } 446 if(best == -1){ 447 best = up[v]; 448 ++ans; 449 } 450 path[v] = best; 451 return ans; 452 } 453 454 int main(){ 455 scanf("%d%d%lld", &n, &L, &S); 456 for(int i = 0; i < n; i++){ 457 scanf("%d", &w[i]); 458 if(w[i] > S){printf("-1"); return 0;} 459 } 460 for(int i = 1; i < n; i++){ 461 int j; 462 scanf("%d", &j); 463 down[--j].push_back(i); 464 } 465 preprocess(0); 466 printf("%d", solve(0)); 467 } 468 ```