codeforces-scrape

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

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