codeforces-scrape

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

2042.md (8655B)


      1 Source: https://codeforces.com/blog/entry/136886
      2 
      3 [2042A - Greedy Monocarp](/contest/2042/problem/A "Educational Codeforces Round 172 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17 
     18 int main() {
     19   int t;
     20   cin >> t;
     21   while (t--) {
     22     int n, k;
     23     cin >> n >> k;
     24     vector<int> a(n);
     25     for (auto& x : a) cin >> x;
     26     sort(a.begin(), a.end(), greater<int>());
     27     int sum = 0;
     28     for (auto& x : a) {
     29       if (sum + x <= k) sum += x;
     30       else break;
     31     }
     32     cout << k - sum << '\n';
     33   }
     34 }
     35 ```
     36 
     37 [2042B - Game with Colored Marbles](/contest/2042/problem/B "Educational Codeforces Round 172 (Rated for Div. 2)")
     38 
     39 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution (BledDest)**
     46 
     47 ```
     48 #include<bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 int main()
     53 {
     54     int t;
     55     scanf("%d", &t);
     56     for(int _ = 0; _ < t; _++)
     57     {
     58         int n;
     59         scanf("%d", &n);
     60         vector<int> c(n);
     61         for(int i = 0; i < n; i++)
     62         {
     63             scanf("%d", &c[i]);
     64             --c[i];
     65         }
     66         vector<int> cnt(n);
     67         for(auto x : c) cnt[x]++;
     68         int exactly1 = 0, morethan1 = 0;
     69         for(auto x : cnt)
     70             if (x == 1)
     71                 exactly1++;
     72             else if(x > 1)
     73                 morethan1++;
     74         printf("%d\n", morethan1 + (exactly1 + 1) / 2 * 2);
     75     }
     76 }
     77 ```
     78 
     79 [2042C - Competitive Fishing](/contest/2042/problem/C "Educational Codeforces Round 172 (Rated for Div. 2)")
     80 
     81 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution (Neon)**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91  
     92 using namespace std;
     93 
     94 int main() {
     95   int t;
     96   cin >> t;
     97   while (t--) {
     98     int n, k;
     99     string s;
    100     cin >> n >> k >> s;
    101     vector<int> vals;
    102     int sum = 0;
    103     for (int i = n - 1; i > 0; --i) {
    104       sum += (s[i] == '1' ? 1 : -1);
    105       if (sum > 0) vals.push_back(sum);
    106     }
    107     sort(vals.begin(), vals.end());
    108     int ans = 1;
    109     while (k > 0 && !vals.empty()) {
    110       k -= vals.back();
    111       vals.pop_back();
    112       ++ans;
    113     }
    114     cout << (k > 0 ? -1 : ans) << '\n';
    115   }
    116 }
    117 ```
    118 
    119 [2042D - Recommendations](/contest/2042/problem/D "Educational Codeforces Round 172 (Rated for Div. 2)")
    120 
    121 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution (adedalic)**
    128 
    129 ```
    130 #include<bits/stdc++.h>
    131 using namespace std;
    132 
    133 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    134 #define sz(a) int((a).size())
    135 
    136 struct Seg {
    137 	int l, r;
    138 
    139 	bool operator< (const Seg &oth) const {
    140 		if (l != oth.l)
    141 			return l < oth.l;
    142 		return r < oth.r;
    143 	};
    144 };
    145 
    146 void solve() {
    147 	int n;
    148 	cin >> n;
    149 	vector<Seg> seg(n);
    150 	for (int i = 0; i < n; i++)
    151 		cin >> seg[i].l >> seg[i].r;
    152 	
    153 	vector<int> ans(n, 0);
    154 	for (int k = 0; k < 2; k++) {
    155 		vector<int> ord(n);
    156 		iota(ord.begin(), ord.end(), 0);
    157 
    158 		sort(ord.begin(), ord.end(), [&seg](int i, int j){
    159 			if (seg[i].l != seg[j].l)
    160 				return seg[i].l < seg[j].l;
    161 			return seg[i].r > seg[j].r;
    162 		});
    163 
    164 		set<int> bounds;
    165 		for (int i : ord) {
    166 			auto it = bounds.lower_bound(seg[i].r);
    167 			if (it != bounds.end())
    168 				ans[i] += *it - seg[i].r;
    169 			bounds.insert(seg[i].r);
    170 		}
    171 
    172 		for (auto &s : seg) {
    173 			s.l = -s.l;
    174 			s.r = -s.r;
    175 			swap(s.l, s.r);
    176 		}
    177 	}
    178 
    179 	map<Seg, int> cnt;
    180 	for (auto s: seg)
    181 		cnt[s]++;
    182 	for (int i = 0; i < n; i++)
    183 		if (cnt[seg[i]] > 1)
    184 			ans[i] = 0;
    185 	
    186 	for (int a : ans)
    187 		cout << a << '\n';
    188 }
    189 
    190 int main() {
    191 	ios_base::sync_with_stdio(false);
    192 	cin.tie(0);
    193 	
    194 	int t; cin >> t;
    195 	while (t--)
    196 		solve();
    197 	return 0;
    198 }
    199 ```
    200 
    201 [2042E - Vertex Pairs](/contest/2042/problem/E "Educational Codeforces Round 172 (Rated for Div. 2)")
    202 
    203 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    204 
    205 **Tutorial**
    206 
    207 Tutorial is loading...
    208 
    209 **Solution (awoo)**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213  
    214 #define forn(i, n) for (int i = 0; i < int(n); i++)
    215  
    216 using namespace std;
    217  
    218 vector<vector<int>> g;
    219  
    220 struct LCA {
    221 	vector<vector<pair<int, int>>> st;
    222 	vector<int> pw;
    223  
    224 	void build(vector<pair<int, int>> a) {
    225 		int n = a.size();
    226 		int lg = 32 - __builtin_clz(n);
    227 		st.resize(lg, vector<pair<int, int>>(n));
    228 		st[0] = a;
    229 		for (int j = 1; j < lg; ++j) {
    230 			for (int i = 0; i < n; ++i) {
    231 				st[j][i] = st[j - 1][i];
    232 				if (i + (1 << (j - 1)) < n)
    233 					st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
    234 			}
    235 		}
    236 		pw.resize(n + 1);
    237 		for (int i = 2; i <= n; ++i)
    238 			pw[i] = pw[i / 2] + 1;
    239 	}
    240  
    241 	vector<int> d, fst, par;
    242 	vector<pair<int, int>> ord;
    243  
    244 	int lca(int v, int u) {
    245 		int l = fst[v], r = fst[u];
    246 		if (l > r) swap(l, r);
    247 		++r;
    248 		int len = pw[r - l];
    249 		assert(len < int(st.size()));
    250 		return min(st[len][l], st[len][r - (1 << len)]).second;
    251 	}
    252  
    253 	void init(int v, int p = -1) {
    254 		if (fst[v] == -1) fst[v] = ord.size();
    255 		ord.push_back({ d[v], v });
    256 		for (int u : g[v]) if (u != p) {
    257 			par[u] = v;
    258 			d[u] = d[v] + 1;
    259 			init(u, v);
    260 			ord.push_back({ d[v], v });
    261 		}
    262 	}
    263  
    264 	LCA(int r = 0) {
    265 		int n = g.size();
    266 		d.resize(n);
    267 		fst.assign(n, -1);
    268 		par.assign(n, -1);
    269 		ord.clear();
    270 		init(r);
    271  
    272 		build(ord);
    273 	}
    274 };
    275 
    276 int main() {
    277 	cin.tie(0);
    278 	ios::sync_with_stdio(false);
    279 	int n;
    280 	cin >> n;
    281 	vector<int> a(2 * n);
    282 	forn(i, 2 * n){
    283 		cin >> a[i];
    284 		--a[i];
    285 	}
    286 	g.resize(2 * n);
    287 	forn(i, 2 * n - 1){
    288 		int v, u;
    289 		cin >> v >> u;
    290 		--v, --u;
    291 		g[v].push_back(u);
    292 		g[u].push_back(v);
    293 	}
    294 	vector<int> l(n, -1), r(n, -1);
    295 	forn(i, 2 * n){
    296 		if (l[a[i]] == -1) l[a[i]] = i;
    297 		else r[a[i]] = i;
    298 	}
    299 	vector<char> res(2 * n, 1);
    300 	forn(rt, 2 * n) if (a[rt] == 0){
    301 		LCA d(rt);
    302 		vector<int> state(2 * n, 0);
    303 		
    304 		auto mark = [&](int v){
    305 			while (v != -1 && state[v] != 1){
    306                 state[v] = 1;
    307 				v = d.par[v];
    308 			}
    309 		};
    310 		auto markdel = [&](int v){
    311 			queue<int> q;
    312 			q.push(v);
    313 			state[v] = -1;
    314 			while (!q.empty()){
    315 				int v = q.front();
    316 				q.pop();
    317 				mark(l[a[v]] ^ r[a[v]] ^ v);
    318 				for (int u : g[v]) if (u != d.par[v] && state[u] == 0){
    319 					state[u] = -1;
    320 					q.push(u);
    321 				}
    322 			}
    323 		};
    324 		
    325 		forn(i, n) mark(d.lca(l[i], r[i]));
    326 		for (int i = 2 * n - 1; i >= 0; --i) if (state[i] == 0)
    327 			markdel(i);
    328 		vector<char> cur(2 * n, 0);
    329         for (int i = 0; i < 2 * n; ++i) if (state[i] == 1)
    330             cur[i] = 1;
    331         reverse(cur.begin(), cur.end());
    332 		res = min(res, cur);
    333 	}
    334 	reverse(res.begin(), res.end());
    335 	cout << count(res.begin(), res.end(), 1) << '\n';
    336 	forn(i, 2 * n) if (res[i])
    337 		cout << i + 1 << " ";
    338 	cout << '\n';
    339 	return 0;
    340 }
    341 ```
    342 
    343 [2042F - Two Subarrays](/contest/2042/problem/F "Educational Codeforces Round 172 (Rated for Div. 2)")
    344 
    345 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    346 
    347 **Tutorial**
    348 
    349 Tutorial is loading...
    350 
    351 **Solution (Neon)**
    352 
    353 ```
    354 #include <bits/stdc++.h>
    355  
    356 using namespace std;
    357 
    358 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    359 
    360 const int N = 200 * 1000 + 13;
    361 const int K = 5;
    362 
    363 using li = long long;
    364 using mat = array<array<li, K>, K>;
    365 
    366 const li INF = 1e18;
    367 
    368 int n, q;
    369 li a[N], b[N];
    370 mat t[4 * N];
    371 
    372 mat init(li a, li b) {
    373   mat c;
    374   forn(i, K) forn(j, i + 1) c[j][i] = -INF;
    375   c[0][0] = c[2][2] = c[4][4] = 0;
    376   c[0][1] = c[2][3] = a + b;
    377   c[0][2] = c[2][4] = a + b + b;
    378   c[1][1] = c[3][3] = a;
    379   c[1][2] = c[3][4] = a + b;
    380   return c;
    381 }
    382 
    383 mat combine(mat a, mat b) {
    384   mat c = init(-INF, -INF);
    385   forn(i, K) forn(j, i + 1) forn(k, j + 1)
    386     c[k][i] = max(c[k][i], a[k][j] + b[j][i]);
    387   return c;
    388 }
    389 
    390 void build(int v, int l, int r) {
    391   if (l + 1 == r) {
    392     t[v] = init(a[l], b[l]);
    393     return;
    394   }
    395   int m = (l + r) / 2;
    396   build(v * 2 + 1, l, m);
    397   build(v * 2 + 2, m, r);
    398   t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
    399 }
    400 
    401 void upd(int v, int l, int r, int p) {
    402   if (l + 1 == r) {
    403     t[v] = init(a[l], b[l]);
    404     return;
    405   }
    406   int m = (l + r) / 2;
    407   if (p < m) upd(v * 2 + 1, l, m, p);
    408   else upd(v * 2 + 2, m, r, p);
    409   t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
    410 }
    411 
    412 mat get(int v, int l, int r, int L, int R) {
    413   if (L >= R) return init(-INF, -INF);
    414   if (l == L && r == R) return t[v];
    415   int m = (l + r) / 2;
    416   return combine(
    417     get(v * 2 + 1, l, m, L, min(m, R)),
    418     get(v * 2 + 2, m, r, max(m, L), R)
    419   );
    420 }
    421 
    422 int main() {
    423   ios::sync_with_stdio(false); cin.tie(0);
    424   cin >> n;
    425   forn(i, n) cin >> a[i];
    426   forn(i, n) cin >> b[i];
    427   build(0, 0, n);
    428   cin >> q;
    429   forn(_, q) {
    430     int t, x, y;
    431     cin >> t >> x >> y;
    432     --x;
    433     if (t == 1) {
    434       a[x] = y;
    435       upd(0, 0, n, x);
    436     } else if (t == 2) {
    437       b[x] = y;
    438       upd(0, 0, n, x);
    439     } else {
    440       auto res = get(0, 0, n, x, y);
    441       cout << res[0][4] << '\n';
    442     }
    443   }
    444 }
    445 ```