1858.md (7988B)
1 Source: https://codeforces.com/blog/entry/119398 2 3 We hope you liked our problems! 4 5 [1858A - Buttons](/contest/1858/problem/A "Codeforces Round 893 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 a, b, c = map(int, input().split()) 17 if c % 2 == 0: 18 if a > b: 19 print("First") 20 else: 21 print("Second") 22 else: 23 if b > a: 24 print("Second") 25 else: 26 print("First") 27 ``` 28 29 [1858B - The Walkway](/contest/1858/problem/B "Codeforces Round 893 (Div. 2)") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Code** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 42 int solve(int d, vector<int> x) 43 { 44 int ans = 0; 45 for (int i = 1; i < x.size(); i++) 46 { 47 ans += (x[i] - x[i - 1] - 1) / d; 48 } 49 ans += int(x.size()) - 2; 50 return ans; 51 } 52 53 void solve() 54 { 55 #define tests 56 57 int n, m, d; 58 cin >> n >> m >> d; 59 vector<int> r(m); 60 for (int i = 0; i < m; i++) cin >> r[i]; 61 r.insert(r.begin(), 1 - d); 62 r.push_back(n + 1); 63 64 int ans = 2e9; 65 vector<int> res; 66 for (int i = 1; i <= m; i++) 67 { 68 int A = r[i] - r[i - 1] - 1; 69 int B = r[i + 1] - r[i] - 1; 70 int C = r[i + 1] - r[i - 1] - 1; 71 int D = C / d - (A / d + B / d); 72 if (D < ans) 73 { 74 ans = D; 75 res.clear(); 76 } 77 if (D == ans) 78 { 79 res.push_back(r[i]); 80 } 81 } 82 cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl; 83 } 84 85 int main() 86 { 87 int t = 1; 88 #ifdef tests 89 cin >> t; 90 #endif 91 while (t--) 92 { 93 solve(); 94 } 95 } 96 ``` 97 98 [1858C - Yet Another Permutation Problem](/contest/1858/problem/C "Codeforces Round 893 (Div. 2)") 99 100 **Tutorial** 101 102 Tutorial is loading... 103 104 **Code** 105 106 ``` 107 #include<iostream> 108 #include<vector> 109 110 using namespace std; 111 112 int main() { 113 int t; 114 cin >> t; 115 while (t--) { 116 int n; 117 cin >> n; 118 vector<int> a(n); 119 int cur = 0; 120 for (int i = 1; i <= n; i += 2) { 121 for (int j = i; j <= n; j *= 2) { 122 a[cur++] = j; 123 } 124 } 125 for (int i = 0; i<n; ++i) { 126 cout << a[i] << " "; 127 } 128 cout << '\n'; 129 } 130 return 0; 131 } 132 ``` 133 134 [1858D - Trees and Segments](/contest/1858/problem/D "Codeforces Round 893 (Div. 2)") 135 136 **Tutorial** 137 138 Tutorial is loading... 139 140 **Code** 141 142 ``` 143 #include <bits/stdc++.h> 144 145 #define int long long 146 147 using namespace std; 148 using ll = long long; 149 150 void solve(); 151 152 template<typename ...Args> 153 void println(Args... args) { 154 apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...)); 155 cout << '\n'; 156 } 157 158 int32_t main() { 159 cin.tie(nullptr); 160 ios_base::sync_with_stdio(false); 161 int t = 1; 162 cin >> t; 163 for (int tc = 0; tc < t; ++tc) { 164 solve(); 165 } 166 return 0; 167 } 168 169 void solve() { 170 int n, k; 171 cin >> n >> k; 172 string s; 173 cin >> s; 174 vector<int> max0by1(n + 1, -1e9); 175 vector<vector<int>> max0pref(n + 1, vector<int>(n + 1)); 176 vector<vector<int>> max0suf(n + 1, vector<int>(n + 1)); 177 for (int l = 0; l < n; ++l) { 178 int cnt1 = 0; 179 for (int r = l + 1; r <= n; ++r) { 180 cnt1 += s[r - 1] == '1'; 181 max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l); 182 max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l); 183 } 184 } 185 for (int r = 0; r <= n; ++r) { 186 for (int cnt = 0; cnt <= n; ++cnt) { 187 if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]); 188 if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]); 189 } 190 } 191 for (int l = n; l >= 0; --l) { 192 for (int cnt = 0; cnt <= n; ++cnt) { 193 if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]); 194 if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]); 195 } 196 } 197 vector<int> ans(n + 1, -1e9); 198 for (int l = 0; l < n; ++l) { 199 int cnt0 = 0; 200 for (int r = l; r <= n; ++r) { 201 if (r > l) cnt0 += s[r - 1] == '0'; 202 if (cnt0 > k) break; 203 max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]); 204 max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]); 205 } 206 } 207 for (int i = 0; i <= n; ++i) { 208 for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a); 209 } 210 for (int i = 1; i <= n; ++i) cout << ans[i] << ' '; 211 cout << '\n'; 212 } 213 ``` 214 215 [1858E2 - Rollbacks (Hard Version)](/contest/1858/problem/E2 "Codeforces Round 893 (Div. 2)") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Code** 222 223 ``` 224 #include <iostream> 225 #include <vector> 226 #include <numeric> 227 #include <set> 228 229 using namespace std; 230 231 const int maxn = 1e6 + 1; 232 233 int f[maxn]; 234 235 int get(int i) { 236 int ans = 0; 237 while (i >= 0) { 238 ans += f[i]; 239 i = (i & (i + 1)) - 1; 240 } 241 return ans; 242 } 243 244 void upd(int i, int x) { 245 while (i < maxn) { 246 f[i] += x; 247 i = i | (i + 1); 248 } 249 } 250 251 int a[maxn]; 252 int rev[maxn]; 253 set<int> ids[maxn]; 254 255 int32_t main() { 256 ios_base::sync_with_stdio(false); 257 cin.tie(0); 258 cout.tie(0); 259 fill(rev, rev + maxn, -1); 260 fill(a, a + maxn, -1); 261 int q; 262 cin >> q; 263 int ptr = -1; 264 vector<pair<pair<int, int>, int>> changes; 265 while (q--) { 266 char t; 267 cin >> t; 268 if (t == '?') { 269 cout << get(ptr) << endl; 270 } else if (t == '+') { 271 int x; 272 cin >> x; 273 int mem = a[ptr + 1]; 274 if (a[ptr + 1] != -1) { 275 if (ids[a[ptr + 1]].size()) { 276 upd(*ids[a[ptr + 1]].begin(), -1); 277 ids[a[ptr + 1]].erase(ptr + 1); 278 } 279 if (ids[a[ptr + 1]].size()) { 280 upd(*ids[a[ptr + 1]].begin(), 1); 281 } 282 } 283 a[ptr + 1] = x; 284 if (a[ptr + 1] != -1) { 285 if (ids[a[ptr + 1]].size()) { 286 upd(*ids[a[ptr + 1]].begin(), -1); 287 } 288 ids[x].insert(ptr + 1); 289 if (ids[a[ptr + 1]].size()) { 290 upd(*ids[a[ptr + 1]].begin(), 1); 291 } 292 } 293 ++ptr; 294 changes.push_back({ { 1, mem }, -1 }); 295 } else if (t == '-') { 296 int k; 297 cin >> k; 298 ptr -= k; 299 changes.push_back({ { -1, k }, -1 }); 300 } else { 301 if (changes.back().first.first == 1) { 302 if (a[ptr] != -1) { 303 if (ids[a[ptr]].size()) { 304 upd(*ids[a[ptr]].begin(), -1); 305 ids[a[ptr]].erase(ptr); 306 } 307 if (ids[a[ptr]].size()) { 308 upd(*ids[a[ptr]].begin(), 1); 309 } 310 } 311 a[ptr] = changes.back().first.second; 312 --ptr; 313 if (a[ptr + 1] != -1) { 314 if (ids[a[ptr + 1]].size()) { 315 upd(*ids[a[ptr + 1]].begin(), -1); 316 } 317 ids[a[ptr + 1]].insert(ptr + 1); 318 if (ids[a[ptr + 1]].size()) { 319 upd(*ids[a[ptr + 1]].begin(), 1); 320 } 321 } 322 } else { 323 ptr += changes.back().first.second; 324 } 325 changes.pop_back(); 326 } 327 } 328 } 329 ``` 330 331 **Note:** At about 20 minutes into the round one of our testers ([SomethingNew](/profile/SomethingNew "Grandmaster SomethingNew")) came up with a linear solution for problem E2, and [jiangly](/profile/jiangly "Legendary Grandmaster jiangly") implemented the same solution shortly after the contest! For further details, see [219001999](/contest/1858/submission/219001999 "Submission 219001999 by jiangly"). The main idea (as [jiangly](/profile/jiangly "Legendary Grandmaster jiangly") pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.