codeforces-scrape

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

1140.md (9923B)


      1 Source: https://codeforces.com/blog/entry/66147
      2 
      3 [1140A - Detective Book](/contest/1140/problem/A "Educational Codeforces Round 62 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (adedalic)**
     10 
     11 ```
     12 #include<bits/stdc++.h>
     13 using namespace std;
     14 
     15 int n;
     16 vector<int> a;
     17 
     18 inline bool read() {
     19 	if(!(cin >> n))
     20 		return false;
     21 	a.resize(n);
     22 	for(int i = 0; i < n; i++) {
     23 		cin >> a[i];
     24 		a[i]--;
     25 	}
     26 	return true;
     27 }
     28 
     29 inline void solve() {
     30 	int cnt = 0, pos = 0;
     31 	while(pos < n) {
     32 		cnt++;
     33 		int mx = pos;
     34 		while(pos < n && pos <= mx) {
     35 			mx = max(mx, a[pos]);
     36 			pos++;
     37 		}
     38 	}
     39 	cout << cnt << endl;
     40 }
     41 
     42 int main() {
     43 #ifdef _DEBUG
     44 	freopen("input.txt", "r", stdin);
     45 #endif	
     46 	if(read()) {
     47 		solve();
     48 	}
     49 	return 0;
     50 }
     51 ```
     52 
     53 [1140B - Good String](/contest/1140/problem/B "Educational Codeforces Round 62 (Rated for Div. 2)")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (Roms)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63 
     64 using namespace std;
     65 
     66 int t, n;
     67 string s;
     68 
     69 int main(){
     70 	cin >> t;
     71 	for(int tc = 0; tc < t; ++tc){
     72 		cin >> n >> s;
     73 		int res = n - 1;
     74 		for(int i = 0; i < n; ++i)
     75 			if(s[i] == '>' || s[n - 1 - i] == '<')
     76 				res = min(res, i);
     77 		
     78 		cout << res << endl;
     79 	}
     80 
     81 	return 0;
     82 }
     83 ```
     84 
     85 [1140C - Playlist](/contest/1140/problem/C "Educational Codeforces Round 62 (Rated for Div. 2)")
     86 
     87 **Tutorial**
     88 
     89 Tutorial is loading...
     90 
     91 **Solution (Roms)**
     92 
     93 ```
     94 #include <bits/stdc++.h>
     95 
     96 using namespace std;
     97 
     98 const int N = 300009;
     99 
    100 int n, k;
    101 pair<int, int> a[N];
    102 
    103 int main() {
    104 	cin >> n >> k;
    105 	
    106 	for(int i = 0; i < n; ++i)
    107 		cin >> a[i].second >> a[i].first;
    108 
    109 	sort(a, a + n);
    110 	long long res = 0;
    111 	long long sum = 0;
    112 	set<pair<int, int> > s;
    113 	for(int i = n - 1; i >= 0; --i){
    114 		s.insert(make_pair(a[i].second, i));
    115 		sum += a[i].second;
    116 		while(s.size() > k){
    117 			auto it = s.begin();
    118 			sum -= it->first;
    119 			s.erase(it);
    120 		}
    121 
    122 		res = max(res, sum * a[i].first);
    123 	}
    124 
    125 	cout << res << endl;
    126 	return 0;
    127 }
    128 ```
    129 
    130 [1140D - Minimum Triangulation](/contest/1140/problem/D "Educational Codeforces Round 62 (Rated for Div. 2)")
    131 
    132 **Tutorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Solution (adedalic)**
    137 
    138 ```
    139 #include<bits/stdc++.h>
    140 using namespace std;
    141 
    142 int main() {
    143 	int n; cin >> n;
    144 
    145 	long long ans = 0;
    146 	for(int id = 2; id < n; id++)
    147 		ans += 1ll * id * (id + 1);
    148 	
    149 	cout << ans << endl;
    150 }
    151 ```
    152 
    153 [1140E - Palindrome-less Arrays](/contest/1140/problem/E "Educational Codeforces Round 62 (Rated for Div. 2)")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution (adedalic)**
    160 
    161 ```
    162 #include<bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    167 #define sz(a) int((a).size())
    168 
    169 #define x first
    170 #define y second
    171 
    172 typedef long long li;
    173 typedef pair<int, int> pt;
    174 
    175 const int MOD = 998244353;
    176 int norm(int a) {
    177     while(a >= MOD) a -= MOD;
    178     while(a < 0) a += MOD;
    179     return a;
    180 }
    181 int mul(int a, int b) {
    182     return int(a * 1ll * b % MOD);
    183 }
    184 
    185 int n, k;
    186 vector<int> a;
    187 
    188 inline bool read() {
    189     if(!(cin >> n >> k))
    190         return false;
    191     a.resize(n);
    192     fore(i, 0, n)
    193         cin >> a[i];
    194     return true;
    195 }
    196 
    197 pair<int, int> calc(int len) {
    198     if(len == 0) return {0, 1};
    199     if(len & 1) {
    200         auto res = calc(len >> 1);
    201         return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
    202                 norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    203     }
    204     auto res = calc(len - 1);
    205     return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
    206 }
    207 
    208 vector<int> curArray;
    209 
    210 int calcSeg(int l, int r) {
    211     if(r >= sz(curArray)) {
    212         int len = r - l - 1, cf = 1;
    213         if(l < 0)
    214             len--, cf = k;
    215         if(len == 0) return cf;
    216 
    217         auto res = calc(len - 1);
    218         return mul(cf, norm(res.x + mul(k - 1, res.y)));
    219     }
    220     if(l < 0) {
    221         if(r - l == 1) return 1;
    222         auto res = calc(r - l - 2);
    223         return norm(res.x + mul(k - 1, res.y));
    224     }
    225     auto res = calc(r - l - 1);
    226     return curArray[l] == curArray[r] ? res.x : res.y;
    227 }
    228 
    229 inline void solve() {
    230     int ans = 1;
    231     fore(k, 0, 2) {
    232         curArray.clear();
    233         for(int i = 0; 2 * i + k < n; i++)
    234             curArray.push_back(a[2 * i + k]);
    235 
    236         int lst = -1;
    237         fore(i, 0, sz(curArray)){
    238             if(curArray[i] == -1) continue;
    239             ans = mul(ans, calcSeg(lst, i));
    240             lst = i;
    241         }
    242         ans = mul(ans, calcSeg(lst, sz(curArray)));
    243     }
    244     cout << ans << endl;
    245 }
    246 
    247 int main() {
    248 #ifdef _DEBUG
    249     freopen("input.txt", "r", stdin);
    250     int tt = clock();
    251 #endif
    252     ios_base::sync_with_stdio(0);
    253     cin.tie(0), cout.tie(0);
    254     cout << fixed << setprecision(15);
    255 
    256     if(read()) {
    257         solve();
    258 
    259 #ifdef _DEBUG
    260         cerr << "TIME = " << clock() - tt << endl;
    261         tt = clock();
    262 #endif
    263     }
    264     return 0;
    265 }
    266 ```
    267 
    268 [1140F - Extending Set of Points](/contest/1140/problem/F "Educational Codeforces Round 62 (Rated for Div. 2)")
    269 
    270 **Tutorial**
    271 
    272 Tutorial is loading...
    273 
    274 **Solution (BledDest)**
    275 
    276 ```
    277 #include <bits/stdc++.h>
    278 
    279 using namespace std;
    280 
    281 typedef long long li;
    282 
    283 #define x first
    284 #define y second
    285 
    286 const int N = 300043;
    287 const int K = 300000;
    288 
    289 int p[2 * N];
    290 int s1[2 * N];
    291 int s2[2 * N];
    292 li ans = 0;
    293 
    294 int* where[80 * N];
    295 int val[80 * N];
    296 int cur = 0;
    297 
    298 void change(int& x, int y)
    299 {
    300 	where[cur] = &x;
    301 	val[cur] = x;
    302 	x = y;
    303 	cur++;
    304 }
    305 
    306 void rollback()
    307 {
    308 	cur--;
    309 	(*where[cur]) = val[cur];
    310 }
    311 
    312 int get(int x)
    313 {
    314 	if(p[x] == x)
    315 		return x;
    316 	return get(p[x]);
    317 }
    318 
    319 void merge(int x, int y)
    320 {
    321 	x = get(x);
    322 	y = get(y);
    323 	if(x == y) return;
    324 	ans -= s1[x] * 1ll * s2[x];
    325 	ans -= s1[y] * 1ll * s2[y];
    326 	if(s1[x] + s2[x] < s1[y] + s2[y])
    327 		swap(x, y);
    328 	change(p[y], x);
    329 	change(s1[x], s1[x] + s1[y]);
    330 	change(s2[x], s2[x] + s2[y]);
    331 	ans += s1[x] * 1ll * s2[x];
    332 }
    333 
    334 void init()
    335 {
    336 	for(int i = 0; i < K; i++)
    337 	{
    338 		p[i] = i;
    339 		p[i + K] = i + K;
    340 		s1[i] = 1;
    341 		s2[i + K] = 1;
    342 	}
    343 }
    344 
    345 vector<pair<int, int> > T[4 * N];
    346 
    347 void add(int v, int l, int r, int L, int R, pair<int, int> val)
    348 {
    349 	if(L >= R) return;
    350 	if(L == l && R == r)
    351 		T[v].push_back(val);
    352 	else
    353 	{
    354 		int m = (l + r) / 2;
    355 		add(v * 2 + 1, l, m, L, min(R, m), val);
    356 		add(v * 2 + 2, m, r, max(m, L), R, val);
    357 	}
    358 }
    359 
    360 li res[N];
    361 
    362 void dfs(int v, int l, int r)
    363 {
    364 	li last_ans = ans;
    365 	int state = cur;
    366 	for(auto x : T[v])
    367 		merge(x.x, x.y + K);
    368 	if(l == r - 1)
    369 		res[l] = ans;
    370 	else
    371 	{
    372 		int m = (l + r) / 2;
    373 		dfs(v * 2 + 1, l, m);
    374 		dfs(v * 2 + 2, m, r);
    375 	}
    376 	while(cur != state) rollback();
    377 	ans = last_ans;
    378 }
    379 
    380 int main()
    381 {
    382 	int q;
    383 	scanf("%d", &q);
    384 	map<pair<int, int>, int> last;
    385 	for(int i = 0; i < q; i++)
    386 	{
    387 		int x, y;
    388 		scanf("%d %d", &x, &y);
    389 		--x;
    390 		--y;
    391 		pair<int, int> p = make_pair(x, y);
    392 		if(last.count(p))
    393 		{
    394 			add(0, 0, q, last[p], i, p);
    395 			last.erase(p);
    396 		}
    397 		else
    398 			last[p] = i;
    399 	}
    400 	for(auto x : last)
    401 		add(0, 0, q, x.y, q, x.x);
    402 	init();
    403 	dfs(0, 0, q);
    404 	for(int i = 0; i < q; i++)
    405 		printf("%I64d ", res[i]);
    406 }
    407 ```
    408 
    409 [1140G - Double Tree](/contest/1140/problem/G "Educational Codeforces Round 62 (Rated for Div. 2)")
    410 
    411 **Tutorial**
    412 
    413 Tutorial is loading...
    414 
    415 **Solution (BledDest)**
    416 
    417 ```
    418 #include <bits/stdc++.h>
    419 
    420 using namespace std;
    421 
    422 typedef long long li;
    423 
    424 #define x first
    425 #define y second
    426 
    427 const int N = 600043;
    428 
    429 li d1[N];
    430 li d2[N][2];
    431 li dist_temp[N][2];
    432 vector<pair<int, int> > g[N];
    433 vector<int> qs[N];
    434 int qq[N][2];
    435 li ans[N];
    436 int n;
    437 int used[N];
    438 int cnt[N];
    439 int last[N];
    440 int cc = 1;
    441 
    442 void preprocess()
    443 {
    444 	set<pair<li, int> > q;
    445 	for(int i = 0; i < n; i++)
    446 		q.insert(make_pair(d1[i], i));
    447 	while(!q.empty())
    448 	{
    449 		int k = q.begin()->second;
    450 		q.erase(q.begin());
    451 		for(auto e : g[k])
    452 		{
    453 			int to = e.first;
    454 			li w = d2[e.second][0] + d2[e.second][1];
    455 			if(d1[to] > w + d1[k])
    456 			{
    457 				q.erase(make_pair(d1[to], to));
    458 				d1[to] = w + d1[k];
    459 				q.insert(make_pair(d1[to], to));
    460 			}
    461 		}
    462 	}
    463 }
    464 
    465 void dfs1(int x, int p = -1)
    466 {
    467 	if(used[x]) return;
    468 	cnt[x] = 1;
    469 	for(auto y : g[x])
    470 	{
    471 		int to = y.first;
    472 		if(!used[to] && to != p)
    473 		{
    474 			dfs1(to, x);
    475 			cnt[x] += cnt[to];
    476 		}
    477 	}
    478 }
    479 
    480 vector<int> cur_queries;
    481 pair<int, int> c;
    482 int S = 0;
    483 
    484 void find_centroid(int x, int p = -1)
    485 {
    486 	if(used[x])	return;
    487 	int mx = 0;
    488 	for(auto y : g[x])
    489 	{
    490 		int to = y.first;
    491 		if(!used[to] && to != p)
    492 		{
    493 			find_centroid(to, x);
    494 			mx = max(mx, cnt[to]);
    495 		}
    496 	}
    497 	if(p != -1)
    498 		mx = max(mx, S - cnt[x]);
    499 	c = min(c, make_pair(mx, x));
    500 }	
    501 
    502 void dfs2(int x, int p = -1, int e = -1)
    503 {
    504 	if(used[x]) return;
    505 	if(p == -1)
    506 	{
    507 		dist_temp[x * 2][0] = dist_temp[x * 2 + 1][1] = 0ll;
    508 		dist_temp[x * 2][1] = dist_temp[x * 2 + 1][0] = d1[x];
    509 	}
    510 	else
    511 	{
    512 		for(int k = 0; k < 2; k++)
    513 		{
    514 			li& D0 = dist_temp[x * 2][k];
    515 			li& D1 = dist_temp[x * 2 + 1][k];
    516 			D0 = dist_temp[p * 2][k] + d2[e][0];
    517 			D1 = dist_temp[p * 2 + 1][k] + d2[e][1];
    518 			D0 = min(D0, D1 + d1[x]);
    519 			D1 = min(D1, D0 + d1[x]); 
    520 		}
    521 	}
    522 	for(auto y : qs[x])
    523 	{
    524 		if(ans[y] != -1) continue;
    525 		if(last[y] == cc)
    526 			cur_queries.push_back(y);
    527 		else
    528 			last[y] = cc;
    529 	}
    530 	for(auto y : g[x])
    531 	{
    532 		int to = y.first;
    533 		if(!used[to] && to != p)
    534 			dfs2(to, x, y.second);
    535 	}
    536 }
    537 
    538 void centroid(int v)
    539 {
    540 	if(used[v]) return;
    541 	dfs1(v);
    542 	S = cnt[v];
    543 	c = make_pair(int(1e9), -1);
    544 	find_centroid(v);
    545 	int C = c.second;
    546 	used[C] = 1;
    547 	for(auto y : g[C])
    548 		centroid(y.first);
    549 	cc++;
    550 	cur_queries.clear();
    551 	used[C] = 0;
    552 	dfs2(C);
    553 	for(auto x : cur_queries)
    554 	{
    555 		int u = qq[x][0];
    556 		int v = qq[x][1];
    557 		ans[x] = min(dist_temp[u][0] + dist_temp[v][0], dist_temp[u][1] + dist_temp[v][1]);
    558 	}
    559 }
    560 
    561 int main()
    562 {
    563 	scanf("%d", &n);
    564 	for(int i = 0; i < n; i++)
    565 		scanf("%I64d", &d1[i]);
    566 	for(int i = 0; i < n - 1; i++)
    567 	{
    568 		int x, y;
    569 		li w1, w2;
    570 		scanf("%d %d %I64d %I64d", &x, &y, &w1, &w2);
    571 		--x;
    572 		--y;
    573 		d2[i][0] = w1;
    574 		d2[i][1] = w2;
    575 		g[x].push_back(make_pair(y, i));
    576 		g[y].push_back(make_pair(x, i));
    577 	}
    578 	int q;
    579 	scanf("%d", &q);
    580 	for(int i = 0; i < q; i++)
    581 	{
    582 		scanf("%d", &qq[i][0]);
    583 		scanf("%d", &qq[i][1]);
    584 		--qq[i][0];
    585 		--qq[i][1];
    586 		qs[qq[i][0] / 2].push_back(i);
    587 		qs[qq[i][1] / 2].push_back(i);
    588 	}
    589 	preprocess();
    590 	for(int i = 0; i < q; i++)
    591 		ans[i] = -1;
    592 	centroid(0);
    593 	for(int i = 0; i < q; i++)
    594 		cout << ans[i] << endl;
    595 }
    596 ```