codeforces-scrape

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

1832.md (7149B)


      1 Source: https://codeforces.com/blog/entry/116454
      2 
      3 [1832A - New Palindrome](/contest/1832/problem/A "Educational Codeforces Round 148 (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     string s;
     23     cin >> s;
     24     s = s.substr(0, s.size() / 2);
     25     int k = unique(s.begin(), s.end()) - s.begin();
     26     cout << (k == 1 ? "NO" : "YES") << '\n';
     27   }
     28 }
     29 ```
     30 
     31 [1832B - Maximum Sum](/contest/1832/problem/B "Educational Codeforces Round 148 (Rated for Div. 2)")
     32 
     33 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     34 
     35 **Tutorial**
     36 
     37 Tutorial is loading...
     38 
     39 **Solution (awoo)**
     40 
     41 ```
     42 for _ in range(int(input())):
     43 	n, k = map(int, input().split())
     44 	a = sorted(list(map(int, input().split())))
     45 	ans = 0
     46 	pr = [0] * (n + 1)
     47 	for i in range(n):
     48 		pr[i + 1] = pr[i] + a[i]
     49 	for i in range(k + 1):
     50 		ans = max(ans, pr[n - (k - i)] - pr[2 * i])
     51 	print(ans)
     52 ```
     53 
     54 [1832C - Contrast Value](/contest/1832/problem/C "Educational Codeforces Round 148 (Rated for Div. 2)")
     55 
     56 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution (Neon)**
     63 
     64 ```
     65 #include <bits/stdc++.h>
     66 
     67 using namespace std;
     68 
     69 int main() {
     70   ios::sync_with_stdio(false); cin.tie(0);
     71   int t;
     72   cin >> t;
     73   while (t--) {
     74     int n;
     75     cin >> n;
     76     vector<int> a(n);
     77     for (int& x : a) cin >> x;
     78     n = unique(a.begin(), a.end()) - a.begin();
     79     int ans = n;
     80     for (int i = 0; i + 2 < n; ++i) {
     81       ans -= (a[i] < a[i + 1] && a[i + 1] < a[i + 2]);
     82       ans -= (a[i] > a[i + 1] && a[i + 1] > a[i + 2]);
     83     }
     84     cout << ans << '\n';
     85   }
     86 }
     87 ```
     88 
     89 [1832D1 - Red-Blue Operations (Easy Version)](/contest/1832/problem/D1 "Educational Codeforces Round 148 (Rated for Div. 2)")
     90 
     91 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     92 
     93 **Tutorial**
     94 
     95 Tutorial is loading...
     96 
     97 [1832D2 - Red-Blue Operations (Hard Version)](/contest/1832/problem/D2 "Educational Codeforces Round 148 (Rated for Div. 2)")
     98 
     99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (awoo)**
    106 
    107 ```
    108 n, q = map(int, input().split())
    109 a = list(map(int, input().split()))
    110 a.sort()
    111 pr = [10**9 for i in range(n + 1)]
    112 for i in range(n):
    113 	pr[i + 1] = min(pr[i], a[i] - i)
    114 s = sum(a) - n * (n - 1) // 2
    115 ans = []
    116 for k in map(int, input().split()):
    117 	if k < n:
    118 		ans.append(min(pr[k] + k, a[k]))
    119 		continue
    120 	if k % 2 == n % 2:
    121 		ns = s - pr[n] * n
    122 		ans.append(pr[n] + k - (max(0, (k - n) // 2 - ns) + n - 1) // n)
    123 	else:
    124 		nmn = min(pr[n - 1], a[n - 1] - k)
    125 		ns = (s + (n - 1) - k) - nmn * n
    126 		ans.append(nmn + k - (max(0, (k - (n - 1)) // 2 - ns) + n - 1) // n)
    127 print(*ans)
    128 ```
    129 
    130 [1832E - Combinatorics Problem](/contest/1832/problem/E "Educational Codeforces Round 148 (Rated for Div. 2)")
    131 
    132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    133 
    134 **Tutorial**
    135 
    136 Tutorial is loading...
    137 
    138 **Solution (BledDest)**
    139 
    140 ```
    141 #include<bits/stdc++.h>
    142 
    143 using namespace std;
    144 
    145 const int MOD = 998244353;
    146 
    147 int add(int x, int y, int mod = MOD)
    148 {
    149 	return ((x + y) % mod + mod) % mod;
    150 }
    151 
    152 int mul(int x, int y, int mod = MOD)
    153 {
    154 	return (x * 1ll * y) % mod;
    155 }
    156 
    157 int binpow(int x, int y, int mod = MOD)
    158 {
    159 	int z = add(1, 0, mod);
    160 	while(y > 0)
    161 	{
    162 		if(y % 2 == 1) z = mul(z, x, mod);
    163 		y /= 2;
    164 		x = mul(x, x, mod);
    165 	}
    166 	return z;
    167 }
    168 
    169 vector<int> psum(vector<int> v)
    170 {
    171 	vector<int> ans(1, 0);
    172 	for(auto x : v) ans.push_back(add(ans.back(), x));
    173 	return ans;
    174 }
    175 
    176 int main()
    177 {
    178 	int n;
    179 	cin >> n;
    180 	vector<int> a(n);
    181 	cin >> a[0];
    182 	int x, y, m, k;
    183 	cin >> x >> y >> m >> k;
    184 	for(int i = 1; i < n; i++)
    185 		a[i] = add(mul(a[i - 1], x, m), y, m);
    186 	
    187 	for(int i = 0; i <= k; i++)
    188 		a = psum(a);
    189 	long long ans = 0;
    190 	
    191 	for(int i = 1; i <= n; i++)
    192 		ans ^= (a[i + 1] * 1ll * i);
    193 	cout << ans << endl;
    194 }
    195 ```
    196 
    197 [1832F - Zombies](/contest/1832/problem/F "Educational Codeforces Round 148 (Rated for Div. 2)")
    198 
    199 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    200 
    201 **Tutorial**
    202 
    203 Tutorial is loading...
    204 
    205 **Solution (awoo)**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 
    210 #define forn(i, n) for (int i = 0; i < int(n); i++)
    211 
    212 using namespace std;
    213 
    214 struct seg{
    215 	int l, r;
    216 };
    217 
    218 int n;
    219 vector<long long> dp_before, dp_cur;
    220 vector<vector<long long>> bst;
    221 
    222 void compute(int l, int r, int optl, int optr){
    223 	if (l > r) return;
    224 	int mid = (l + r) / 2;
    225 	pair<long long, int> best = {-1, -1};
    226 	for (int k = optl; k <= min(mid, optr); k++)
    227 		best = max(best, {(k ? dp_before[k - 1] : 0) + bst[k][mid], k});
    228 	dp_cur[mid] = best.first;
    229 	int opt = best.second;
    230 	compute(l, mid - 1, optl, opt);
    231 	compute(mid + 1, r, opt, optr);
    232 }
    233 
    234 struct node{
    235     long long c0;
    236     int c1;
    237 };
    238 
    239 vector<node> f;
    240 
    241 void update(int x, int a, int b){
    242 	for (int i = x; i < int(f.size()); i |= i + 1){
    243 		f[i].c0 += b;
    244 		f[i].c1 += a;
    245 	}
    246 }
    247 
    248 void update(int l, int r, int a, int b){
    249 	update(l, a, b);
    250 	update(r, -a, -b);
    251 }
    252 
    253 long long get(int pos, int x){
    254 	long long res = 0;
    255 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    256 		res += f[i].c0 + f[i].c1 * 1ll * pos;
    257 	return res;
    258 }
    259 
    260 int main() {
    261 	int k, x, m;
    262 	scanf("%d%d%d%d", &n, &k, &x, &m);
    263 	vector<seg> a(n);
    264 	forn(i, n) scanf("%d%d", &a[i].l, &a[i].r);
    265 	sort(a.begin(), a.end(), [&](const seg &a, const seg &b){
    266 		return a.l + a.r < b.l + b.r;
    267 	});
    268 	
    269 	vector<int> pos;
    270 	forn(i, n){
    271 		pos.push_back(a[i].l);
    272 		pos.push_back(a[i].r - m);
    273 	}
    274 	sort(pos.begin(), pos.end());
    275 	pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    276 	int cds = pos.size();
    277 	
    278 	vector<array<int, 4>> npos(n);
    279 	forn(i, n){
    280 		npos[i][0] = lower_bound(pos.begin(), pos.end(), a[i].l - m) - pos.begin();
    281 		npos[i][1] = lower_bound(pos.begin(), pos.end(), a[i].l) - pos.begin();
    282 		npos[i][2] = lower_bound(pos.begin(), pos.end(), a[i].r - m) - pos.begin();
    283 		npos[i][3] = lower_bound(pos.begin(), pos.end(), a[i].r) - pos.begin();
    284 	}
    285 	
    286 	vector<long long> pr(n + 1);
    287 	forn(i, n) pr[i + 1] = pr[i] + x - (m + a[i].r - a[i].l);
    288 	
    289 	auto upd = [&](int i){
    290 		if (a[i].r - a[i].l >= m){
    291 			update(npos[i][0], npos[i][1], 1, m - a[i].l);
    292 			update(npos[i][1], npos[i][2], 0, m);
    293 			update(npos[i][2], npos[i][3], -1, a[i].r);
    294 		}
    295 		else{
    296 			update(npos[i][0], npos[i][2], 1, m - a[i].l);
    297 			update(npos[i][2], npos[i][1], 0, a[i].r - a[i].l);
    298 			update(npos[i][1], npos[i][3], -1, a[i].r);
    299 		}
    300 	};
    301 	
    302 	bst.resize(n, vector<long long>(n, -1));
    303 	vector<vector<int>> opt(n, vector<int>(n));
    304 	forn(r, n) for (int l = r; l >= 0; --l){
    305 		if (l == r) f.assign(cds, {0, 0});
    306 		upd(l);
    307 		int L = (l == r ? (l == 0 ? 0 : opt[l - 1][l - 1]) : opt[l][r - 1]);
    308 		int R = (l == r ? int(pos.size()) - 1 : opt[l + 1][r]);
    309 		for (int k = L; k <= R; ++k){
    310 			long long cur = pr[r + 1] - pr[l] + get(pos[k], k);
    311 			if (cur > bst[l][r]){
    312 				bst[l][r] = cur;
    313 				opt[l][r] = k;
    314 			}
    315 		}
    316 	}
    317 	
    318 	dp_before.resize(n);
    319 	dp_cur.resize(n);
    320 	for (int i = 0; i < n; i++)
    321 		dp_before[i] = bst[0][i];
    322 
    323 	for (int i = 1; i < k; i++){
    324 		compute(0, n - 1, 0, n - 1);
    325 		dp_before = dp_cur;
    326 	}
    327 	
    328 	printf("%lld\n", dp_before[n - 1]);
    329 	return 0;
    330 }
    331 ```