codeforces-scrape

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

2026.md (10588B)


      1 Source: https://codeforces.com/blog/entry/135680
      2 
      3 [2026A - Perpendicular Segments](/contest/2026/problem/A "Educational Codeforces Round 171 (Rated for Div. 2)")
      4 
      5 Idea: [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16  
     17 int main() {
     18 	int t; cin >> t;
     19 	while (t--) {
     20 		int X, Y, K;
     21 		cin >> X >> Y >> K;
     22 		int M = min(X, Y);
     23 		cout << "0 0 " << M << " " << M << endl;
     24 		cout << "0 " << M << " " << M << " 0" << endl;
     25 	}
     26 }
     27 ```
     28 
     29 [2026B - Black Cells](/contest/2026/problem/B "Educational Codeforces Round 171 (Rated for Div. 2)")
     30 
     31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     32 
     33 **Tutorial**
     34 
     35 Tutorial is loading...
     36 
     37 **Solution (Neon)**
     38 
     39 ```
     40 #include <bits/stdc++.h>
     41  
     42 using namespace std;
     43  
     44 int main() {
     45   int t;
     46   cin >> t;
     47   while (t--) {
     48     int n;
     49     cin >> n;
     50     vector<long long> a(n);
     51     for (auto& x : a) cin >> x;
     52     
     53     long long ans = 1e18;
     54     
     55     auto upd = [&](vector<long long> a) {
     56       sort(a.begin(), a.end());
     57       for (int i = 1; i < (int)a.size(); ++i)
     58         if (a[i - 1] == a[i]) return;
     59       long long res = 0;
     60       for (int i = 0; i < (int)a.size(); i += 2)
     61         res = max(res, a[i + 1] - a[i]);
     62       ans = min(ans, res);
     63     };
     64     
     65     if (n % 2 == 0) {
     66       upd(a);
     67       cout << ans << '\n';
     68       continue;
     69     }
     70     
     71     for (int i = 0; i < n; ++i) {
     72       for (int x : {-1, 1}) {
     73         a.push_back(a[i] + x);
     74         upd(a);
     75         a.pop_back();
     76       }
     77     }
     78     
     79     cout << ans << '\n';
     80   }
     81 }
     82 ```
     83 
     84 [2026C - Action Figures](/contest/2026/problem/C "Educational Codeforces Round 171 (Rated for Div. 2)")
     85 
     86 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     87 
     88 **Tutorial**
     89 
     90 Tutorial is loading...
     91 
     92 **Solution (BledDest)**
     93 
     94 ```
     95 #include<bits/stdc++.h>
     96  
     97 using namespace std;
     98  
     99 const int N = 400043;
    100 char buf[N];
    101  
    102 bool can(const string& s, int k)
    103 {
    104     int n = s.size();
    105     vector<int> used(n);
    106     for(int i = n - 1; i >= 0; i--)
    107         if(k > 0 && s[i] == '1')
    108         {
    109             used[i] = 1;
    110             k--;
    111         }
    112     int cur = 0;
    113     for(int i = 0; i < n; i++)
    114         if(used[i])
    115         {
    116             cur--;
    117             if(cur < 0) return false;
    118         }
    119         else cur++;
    120     return true;
    121 }   
    122  
    123 void solve()
    124 {
    125     int n;
    126     scanf("%d", &n);
    127     scanf("%s", buf);                         
    128     if(n == 1)
    129     {
    130         puts("1");
    131         return;
    132     }
    133     string s = buf;
    134     int count_1 = 0;
    135     for(auto x : s) if (x == '1') count_1++;
    136     int l = 1;
    137     int r = count_1 + 1;
    138     while(r - l > 1)
    139     {
    140         int mid = (l + r) / 2;
    141         if(can(s, mid))
    142             l = mid;
    143         else
    144             r = mid;
    145     }
    146     long long ans = 0;
    147     for(int i = n - 1; i >= 0; i--)
    148         if(s[i] == '1' && l > 0)
    149             l--;
    150         else
    151             ans += (i + 1);
    152     printf("%lld\n", ans);
    153 }
    154  
    155 int main()
    156 {
    157     int t;
    158     scanf("%d", &t);
    159     for(int i = 0; i < t; i++)
    160         solve();
    161 }
    162 ```
    163 
    164 [2026D - Sums of Segments](/contest/2026/problem/D "Educational Codeforces Round 171 (Rated for Div. 2)")
    165 
    166 Idea: [shnirelman](/profile/shnirelman "International Grandmaster shnirelman")
    167 
    168 **Tutorial**
    169 
    170 Tutorial is loading...
    171 
    172 **Solution (BledDest)**
    173 
    174 ```
    175 #include<bits/stdc++.h>
    176  
    177 using namespace std;
    178  
    179 const int MOD = 998244353;
    180  
    181 int n;
    182  
    183 vector<long long> a;
    184 vector<long long> pa;
    185 vector<long long> ppa;
    186 vector<long long> start;
    187 vector<long long> block;
    188 vector<long long> pblock;
    189  
    190 vector<long long> prefix_sums(vector<long long> v)
    191 {
    192  	int k = v.size();
    193  	vector<long long> res(k + 1);
    194  	for(int i = 0; i < k; i++) res[i + 1] = res[i] + v[i];
    195  	return res;
    196 }
    197  
    198 long long get_partial(int l, int r1, int r2)
    199 {
    200 	// s(l, r1) + s(l, r1 + 1) + ... + s(l, r2 - 1)
    201  	if(r2 <= r1) return 0ll;
    202  	int cnt = r2 - r1;
    203  	long long rem = pa[l] * cnt;
    204  	long long add = ppa[r2 + 1] - ppa[r1 + 1];
    205  	return add - rem;
    206 }
    207  
    208 pair<int, int> convert(long long i)
    209 {
    210 	int idx = upper_bound(start.begin(), start.end(), i) - start.begin() - 1;
    211 	pair<int, int> res = {idx, i - start[idx] + idx};
    212 	return res; 	
    213 }
    214  
    215 long long query(long long l, long long r)
    216 {
    217 	pair<int, int> lf = convert(l);
    218 	pair<int, int> rg = convert(r);
    219 	long long res = pblock[rg.first + 1] - pblock[lf.first];
    220 	if(lf.second != lf.first) res -= get_partial(lf.first, lf.first, lf.second);
    221 	if(rg.second != n - 1) res -= get_partial(rg.first, rg.second + 1, n);
    222 	return res;	
    223 }
    224  
    225 int main()
    226 {
    227 	scanf("%d", &n);
    228 	a.resize(n);
    229 	for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    230 	pa = prefix_sums(a);
    231 	ppa = prefix_sums(pa);
    232 	start = {0};
    233 	for(int i = n; i >= 1; i--)
    234 		start.push_back(start.back() + i);
    235 	block.resize(n);
    236 	for(int i = 0; i < n; i++)
    237 		block[i] = get_partial(i, i, n);
    238 	pblock = prefix_sums(block);
    239 	int q;
    240 	scanf("%d", &q);
    241 	for(int i = 0; i < q; i++)
    242 	{
    243 	 	long long l, r;
    244 	 	scanf("%lld %lld", &l, &r);
    245 	 	printf("%lld\n", query(l - 1, r - 1));
    246 	}
    247  
    248 }
    249 ```
    250 
    251 [2026E - Best Subsequence](/contest/2026/problem/E "Educational Codeforces Round 171 (Rated for Div. 2)")
    252 
    253 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    254 
    255 **Tutorial**
    256 
    257 Tutorial is loading...
    258 
    259 **Solution (Neon)**
    260 
    261 ```
    262 #include <bits/stdc++.h>
    263  
    264 using namespace std;
    265  
    266 #define sz(a) int((a).size())
    267  
    268 template<typename T = int>
    269 struct Dinic {
    270   struct edge {
    271     int u, rev;
    272     T cap, flow;
    273   };
    274   
    275   int n, s, t;
    276   T flow;
    277   vector<int> lst;
    278   vector<int> d;
    279   vector<vector<edge>> g;
    280   
    281   Dinic() {}
    282   
    283   Dinic(int n, int s, int t) : n(n), s(s), t(t) {
    284     g.resize(n);
    285     d.resize(n);
    286     lst.resize(n);
    287     flow = 0;
    288   }
    289  
    290   void add_edge(int v, int u, T cap, bool directed = true) {
    291     g[v].push_back({u, sz(g[u]), cap, 0});
    292     g[u].push_back({v, sz(g[v]) - 1, directed ? 0 : cap, 0});
    293   }
    294  
    295   T dfs(int v, T flow) {
    296     if (v == t) return flow;
    297     if (flow == 0) return 0;
    298     T result = 0;
    299     for (; lst[v] < sz(g[v]); ++lst[v]) {
    300       edge& e = g[v][lst[v]];
    301       if (d[e.u] != d[v] + 1) continue;
    302       T add = dfs(e.u, min(flow, e.cap - e.flow));
    303       if (add > 0) {
    304         result += add;
    305         flow -= add;
    306         e.flow += add;
    307         g[e.u][e.rev].flow -= add;
    308       }
    309       if (flow == 0) break;
    310     }
    311     return result;
    312   }
    313  
    314   bool bfs() {
    315     fill(d.begin(), d.end(), -1);
    316     queue<int> q({s});
    317     d[s] = 0;
    318     while (!q.empty() && d[t] == -1) {
    319       int v = q.front(); q.pop();
    320       for (auto& e : g[v]) {
    321         if (d[e.u] == -1 && e.cap - e.flow > 0) {
    322           q.push(e.u);
    323           d[e.u] = d[v] + 1;
    324         }
    325       }
    326     }
    327     return d[t] != -1;
    328   }
    329  
    330   T calc() {
    331     T add;
    332     while (bfs()) {
    333       fill(lst.begin(), lst.end(), 0);
    334       while((add = dfs(s, numeric_limits<T>::max())) > 0)
    335         flow += add;
    336     }
    337     return flow;
    338   }
    339 };
    340  
    341 const int B = 60;
    342 const int INF = 1e9;
    343  
    344 int main() {
    345   int t;
    346   cin >> t;
    347   while (t--) {
    348     int n;
    349     cin >> n;
    350     int s = n + B, t = n + B + 1;
    351     Dinic mf(t + 1, s, t);
    352     for (int i = 0; i < n; ++i) {
    353       long long x;
    354       cin >> x;
    355       mf.add_edge(s, i, 1);
    356       for (int j = 0; j < B; ++j) {
    357         if ((x >> j) & 1) mf.add_edge(i, j + n, INF);
    358       }
    359     }
    360     for (int i = 0; i < B; ++i) mf.add_edge(i + n, t, 1);
    361     cout << n - mf.calc() << '\n';
    362   }
    363 }
    364 ```
    365 
    366 [2026F - Bermart Ice Cream](/contest/2026/problem/F "Educational Codeforces Round 171 (Rated for Div. 2)")
    367 
    368 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    369 
    370 **Tutorial**
    371 
    372 Tutorial is loading...
    373 
    374 **Solution (awoo)**
    375 
    376 ```
    377 #include <bits/stdc++.h>
    378  
    379 #define forn(i, n) for (int i = 0; i < int(n); i++)
    380  
    381 using namespace std;
    382  
    383 const int P = 2000 + 5;
    384  
    385 struct item{
    386 	int p, t;
    387 };
    388  
    389 struct minstack {
    390 	stack<item> st;
    391 	stack<array<int, P>> dp;
    392 	int get(int p) {return dp.empty() ? 0 : dp.top()[p];}
    393 	bool empty() {return st.empty();}
    394 	int size() {return st.size();}
    395 	void push(item it) {
    396 		if (empty()){
    397 		    dp.push({});
    398 		    for (int i = 0; i < P; ++i)
    399 		        dp.top()[i] = 0;
    400 		}
    401 		else{
    402 		    dp.push(dp.top());
    403 		}
    404 		st.push(it);
    405 		for (int i = P - it.p - 1; i >= 0; --i)
    406 			dp.top()[i + it.p] = max(dp.top()[i + it.p], dp.top()[i] + it.t);
    407 	}
    408 	void pop() {
    409 		st.pop();
    410 		dp.pop();
    411 	}
    412 	item top() {
    413 		return st.top();
    414 	}
    415 	void swap(minstack &x) {
    416 		st.swap(x.st);
    417 		dp.swap(x.dp);
    418 	}
    419 };
    420  
    421 struct mindeque {
    422 	minstack l, r, t;
    423 	void rebalance() {
    424 		bool f = false;
    425 		if (r.empty()) {f = true; l.swap(r);}
    426 		int sz = r.size() / 2;
    427 		while (sz--) {t.push(r.top()); r.pop();}
    428 		while (!r.empty()) {l.push(r.top()); r.pop();}
    429 		while (!t.empty()) {r.push(t.top()); t.pop();}
    430 		if (f) l.swap(r);
    431 	}
    432 	int get(int p) {
    433 		int ans = 0;
    434 		for (int i = 0; i <= p; ++i)
    435 			ans = max(ans, l.get(i) + r.get(p - i));
    436 		return ans;
    437 	}
    438 	bool empty() {return l.empty() && r.empty();}
    439 	int size() {return l.size() + r.size();}
    440 	void push_front(item it) {l.push(it);}
    441 	void push_back(item it) {r.push(it);}
    442 	void pop_front() {if (l.empty()) rebalance(); l.pop();}
    443 	void pop_back() {if (r.empty()) rebalance(); r.pop();}
    444 	item front() {if (l.empty()) rebalance(); return l.top();}
    445 	item back() {if (r.empty()) rebalance(); return r.top();}
    446 	void swap(mindeque &x) {l.swap(x.l); r.swap(x.r);}
    447 };
    448  
    449 struct edge{
    450 	int u, tp, p, t;
    451 };
    452  
    453 struct query{
    454 	int i, p;
    455 };
    456  
    457 vector<vector<edge>> g;
    458 vector<vector<query>> qs;
    459 vector<int> ans;
    460 mindeque ks;
    461  
    462 void dfs(int v){
    463 	for (auto& [i, p] : qs[v]){
    464 		ans[i] = ks.get(p);
    465 	}
    466 	for (auto& [u, tp, p, t] : g[v]){
    467 		if (tp == 0){
    468 			dfs(u);
    469 		}
    470 		else if (tp == -1){
    471 		    auto it = ks.front();
    472 		    ks.pop_front();
    473 			dfs(u);
    474 			ks.push_front({it.p, it.t});
    475 		}
    476 		else{
    477 			ks.push_back({p, t});
    478 			dfs(u);
    479 			ks.pop_back();
    480 		}
    481 	}
    482 }
    483  
    484 int main() {
    485 	cin.tie(0);
    486 	ios::sync_with_stdio(false);
    487 	int q;
    488 	cin >> q;
    489 	vector<int> st(1);
    490 	vector<int> where(q, -1);
    491 	int cnt = 1, cnt_real = 1;
    492 	where[0] = 0;
    493 	g.push_back({});
    494 	qs.push_back({});
    495 	
    496 	auto copy_shop = [&](int x, bool real){
    497 		g.push_back({});
    498 		qs.push_back({});
    499 		st.push_back(st[x]);
    500 		if (real){
    501 			where[cnt_real] = cnt;
    502 			++cnt_real;
    503 		}
    504 		++cnt;
    505 	};
    506 	
    507 	forn(i, q){
    508 		int tp, x;
    509 		cin >> tp >> x;
    510 		--x;
    511 		int v = where[x], u = -1;
    512 		if (tp != 4){
    513 			copy_shop(v, tp == 1);
    514 			u = cnt - 1;
    515 		}
    516 		if (tp == 1){
    517 			g[v].push_back({u, 0, -1, -1});
    518 			continue;
    519 		}
    520 		if (tp == 3){
    521 			g[v].push_back({u, -1, -1, -1});
    522 			++st[u];
    523 			where[x] = u;
    524 			continue;
    525 		}
    526 		int p;
    527 		cin >> p;
    528 		if (tp == 4){
    529 			qs[v].push_back({i, p});
    530 			continue;
    531 		}
    532 		int t;
    533 		cin >> t;
    534 		g[v].push_back({u, 1, p, t});
    535 		where[x] = u;
    536 	}
    537 	
    538 	ans.assign(q, -1);
    539 	dfs(0);
    540 	forn(i, q) if (ans[i] != -1) cout << ans[i] << '\n';
    541 	return 0;
    542 }
    543 ```