1978.md (7174B)
1 Source: https://codeforces.com/blog/entry/130527 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 #include <random> 9 #include <vector> 10 #include <iostream> 11 #include <set> 12 #include <map> 13 #include <algorithm> 14 15 using namespace std; 16 17 #define fi first 18 #define se second 19 #define all(x) (x).begin(), (x).end() 20 #define ll long long 21 #define pii pair<int, int> 22 #define pb emplace_back 23 24 int main() { 25 int t; 26 cin >> t; 27 while (t--) { 28 int n; 29 cin >> n; 30 vector<int> a(n); 31 for (auto &c : a) cin >> c; 32 int mx = 0; 33 for (int i = 0; i < n - 1; i++) mx = max(mx, a[i]); 34 cout << mx + a[n - 1] << "\n"; 35 } 36 return 0; 37 } 38 ``` 39 40 Tutorial is loading... 41 42 **Code** 43 44 ``` 45 #include <iostream> 46 47 using namespace std; 48 49 int main() { 50 int t; 51 cin >> t; 52 while (t--) { 53 long long n, a, b; 54 cin >> n >> a >> b; 55 if (b <= a) { 56 cout << n * a << endl; 57 } else { 58 long long k = min(b — a + 1, n); 59 cout << (b — k + 1) * n + k * (k — 1) / 2 << endl; 60 } 61 } 62 } 63 ``` 64 65 Tutorial is loading... 66 67 **Code** 68 69 ``` 70 #include <bits/stdc++.h> 71 using namespace std; 72 typedef long long ll; 73 int main() { 74 ios::sync_with_stdio(false); 75 cin.tie(0), cout.tie(0); 76 int T = 1; 77 cin >> T; 78 while (T--) { 79 int n; 80 ll k; 81 cin >> n >> k; 82 ll max_s = 0; 83 for (int i = 0; i < n; i++) max_s += abs(n — 1 — i — i); 84 if (k % 2 != 0 || k > max_s) { 85 cout << "No\n"; 86 } else { 87 cout << "Yes\n"; 88 vector<int> p(n); 89 k /= 2; 90 iota(p.begin(), p.end(), 0); 91 for (int i = 0; k > 0; i++) { 92 if (k >= n — 1 — 2 * i) { 93 swap(p[i], p[n — 1 — i]); 94 k -= n — 1 — 2 * i; 95 } else { 96 swap(p[i], p[i + k]); 97 k = 0; 98 } 99 } 100 for (int i = 0; i < n; i++) { 101 cout << p[i] + 1 << " "; 102 } 103 cout << "\n"; 104 } 105 } 106 } 107 ``` 108 109 Tutorial is loading... 110 111 **Code** 112 113 ``` 114 #include <bits/stdc++.h> 115 116 using namespace std; 117 using ll = long long; 118 119 void solve() { 120 int n, c; 121 cin >> n >> c; 122 123 vector<int> a(n); 124 for (int i = 0; i < n; ++i) { 125 cin >> a[i]; 126 } 127 128 if (n == 1) { 129 cout << "0\n"; 130 return; 131 } 132 133 int mx = *max_element(a.begin() + 1, a.end()); 134 int mxc = max(a[0] + c, mx); 135 int winner = mxc == a[0] + c ? 0 : find(a.begin() + 1, a.end(), mx) - a.begin(); 136 ll sum = c; 137 for (int i = 0; i < n; sum += a[i], ++i) { 138 int answer; 139 if (i == winner) { 140 answer = 0; 141 } else if (sum + a[i] >= mx) { 142 answer = i; 143 } else { 144 answer = i + 1; 145 } 146 cout << answer << " \n"[i == n - 1]; 147 } 148 } 149 150 int main() { 151 ios::sync_with_stdio(false); 152 cin.tie(nullptr); 153 154 int test = 1; 155 cin >> test; 156 157 while (test--) { 158 solve(); 159 } 160 161 return 0; 162 } 163 ``` 164 165 Tutorial is loading... 166 167 **Code** 168 169 ``` 170 #include <bits/stdc++.h> 171 using namespace std; 172 173 int main () { 174 ios_base::sync_with_stdio(0); cin.tie(0); 175 int T; 176 cin >> T; 177 while (T--) { 178 int n; 179 string s, t; 180 cin >> n >> s >> t; 181 auto get_range = [&] (int i) { 182 if (s[i] == '1') return make_pair(i, i); 183 int l = -1, r = -1; 184 if (i > 0 && t[i-1] == '1') l = i-1; 185 else if (i > 1 && t[i-1] == '0' && s[i-2] == '0') l = i-2; 186 if (i+1 < n && t[i+1] == '1') r = i+1; 187 else if (i+2 < n && t[i+1] == '0' && s[i+2] == '0') r = i+2; 188 if (l == -1) r = -1; 189 if (r == -1) l = -1; 190 return make_pair(l, r); 191 }; 192 193 vector<int> pref(n+1); 194 for (int i = 0; i < n; i++) pref[i+1] = pref[i] + (get_range(i).first != -1); 195 196 int q; 197 cin >> q; 198 while (q--) { 199 int l, r; 200 cin >> l >> r; 201 int ans = 0; 202 if (r-l <= 5) { 203 for (int i = l-1; i < r; i++) { 204 auto [ll, rr] = get_range(i); 205 if (ll >= l-1 && rr < r) ans++; 206 } 207 } 208 else { 209 ans = pref[r] - pref[l-1]; 210 for (int j: {l-1, l, r-2, r-1}) { 211 auto [ll, rr] = get_range(j); 212 if (ll != -1 && (ll < l-1 || rr >= r)) ans--; 213 } 214 } 215 cout << ans << '\n'; 216 } 217 } 218 } 219 ``` 220 221 Tutorial is loading... 222 223 **Code** 224 225 ``` 226 #include <iostream> 227 #include <vector> 228 #include <map> 229 #include <set> 230 #include <queue> 231 #include <algorithm> 232 #include <string> 233 #include <cmath> 234 #include <cstdio> 235 #include <iomanip> 236 #include <fstream> 237 #include <cassert> 238 #include <cstring> 239 #include <unordered_set> 240 #include <unordered_map> 241 #include <numeric> 242 #include <ctime> 243 244 using namespace std; 245 246 using ll = long long; 247 248 const int MAXA = 1e6; 249 250 int n, k; 251 vector<int> a; 252 vector<int> primes_x[MAXA + 1]; 253 unordered_map<int, int> last_ind_p; 254 vector<bool> is_prime(MAXA + 1, true); 255 vector<int> primes; 256 257 void read() { 258 cin >> n >> k; 259 a.assign(n, 0); 260 for (int& elem : a) { 261 cin >> elem; 262 } 263 } 264 265 vector<int> p, sz, p_rs; 266 267 int col(int A) { 268 return (A == p[A] ? A : p[A] = col(p[A])); 269 } 270 271 void unique(int A, int B) { 272 A = col(A); B = col(B); 273 if (A == B) return; 274 if (sz[A] < sz[B]) { 275 swap(A, B); 276 } 277 p[B] = A; 278 sz[A] += sz[B]; 279 } 280 281 void solve() { 282 last_ind_p.clear(); 283 vector<int> aa; 284 for (int i = 1; i < n; i++) { 285 aa.push_back(a[i]); 286 } 287 for (int i = 0; i < n; i++) { 288 aa.push_back(a[i]); 289 } 290 a = aa; 291 int n2 = n; 292 n = a.size(); 293 p.assign(n, -1); 294 p_rs.assign(n, -1); 295 sz.assign(n, -1); 296 for (int i = 0; i < n; i++) { 297 p[i] = i; 298 sz[i] = 1; 299 } 300 301 for (int i = 0; i < n2; i++) { 302 p_rs[i] = i + 1; 303 p_rs[2 * n2 - 2 - i] = i + 1; 304 } 305 vector<int> a2 = a; 306 sort(a2.begin(), a2.end()); 307 a2.resize(unique(a2.begin(), a2.end()) - a2.begin()); 308 unordered_set<int> to_clean; 309 for (int elem : a2) { 310 int cur_elem = elem; 311 for (ll p : primes) { 312 if (p * p > elem) break; 313 if (elem % p == 0) { 314 primes_x[cur_elem].push_back(p); 315 if (primes_x[cur_elem].size() == 1) { 316 to_clean.insert(cur_elem); 317 } 318 } 319 while (elem % p == 0) { 320 elem /= p; 321 } 322 } 323 if (elem > 1) { 324 primes_x[cur_elem].push_back(elem); 325 if (primes_x[cur_elem].size() == 1) { 326 to_clean.insert(cur_elem); 327 } 328 } 329 } 330 331 for (int i = 0; i < n; i++) { 332 for (int cur_p : primes_x[a[i]]) { 333 if (last_ind_p.count(cur_p) && i - last_ind_p[cur_p] <= k) { 334 unique(last_ind_p[cur_p], i); 335 } 336 last_ind_p[cur_p] = i; 337 } 338 } 339 for (int i : to_clean) 340 primes_x[i].clear(); 341 } 342 343 void write() { 344 ll ans = 0; 345 for (int i = 0; i < n; i++) { 346 if (p[i] == i) { 347 if (a[i] > 1) { 348 ans += 1; 349 } 350 else { 351 ans += p_rs[i]; 352 } 353 } 354 } 355 cout << ans << endl; 356 } 357 358 int main() { 359 for (ll i = 2; i <= MAXA; i++) { 360 if (is_prime[i]) { 361 primes.push_back(i); 362 for (ll j = i * i; j <= MAXA; j += i) { 363 is_prime[j] = false; 364 } 365 } 366 } 367 ios_base::sync_with_stdio(false); cin.tie(0); 368 int t; 369 cin >> t; 370 while (t--) { 371 read(); 372 solve(); 373 write(); 374 } 375 } 376 ```