codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```