2000.md (10394B)
1 Source: https://codeforces.com/blog/entry/132689 2 3 [2000A - Primary Task](/contest/2000/problem/A "Codeforces Round 966 (Div. 3)") 4 5 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 for _ in range(int(input())): 15 a = int(input()) 16 if 102 <= a <= 109 or 1010 <= a <= 1099: 17 print("YES") 18 else: 19 print("NO") 20 ``` 21 22 [2000B - Seating in a Bus](/contest/2000/problem/B "Codeforces Round 966 (Div. 3)") 23 24 Idea: [myav](/profile/myav "Pupil myav") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution** 31 32 ``` 33 #include <bits/stdc++.h> 34 using namespace std; 35 void solve(){ 36 int n; 37 cin >> n; 38 vector<int>a(n); 39 for(auto &i : a) cin >> i; 40 int left = a[0], right = a[0]; 41 for(int i = 1; i < n; i++){ 42 if(a[i] + 1 == left) left = a[i]; 43 else if(a[i] - 1 == right) right = a[i]; 44 else { 45 cout << "NO\n"; 46 return; 47 } 48 } 49 cout << "YES\n"; 50 } 51 52 int main(){ 53 int t; 54 cin >> t; 55 while (t--) { 56 solve(); 57 } 58 return 0; 59 } 60 ``` 61 62 [2000C - Numeric String Template](/contest/2000/problem/C "Codeforces Round 966 (Div. 3)") 63 64 Idea: [myav](/profile/myav "Pupil myav") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution** 71 72 ``` 73 def solve(): 74 n = int(input()) 75 a = list(map(int, input().split())) 76 m = int(input()) 77 for _ in range(m): 78 m_1 = {} 79 m_2 = {} 80 s = input().strip() 81 if len(s) != n: 82 print("NO") 83 continue 84 85 ok = True 86 for j in range(n): 87 if s[j] not in m_1 and a[j] not in m_2: 88 m_1[s[j]] = a[j] 89 m_2[a[j]] = s[j] 90 elif (s[j] in m_1 and m_1[s[j]] != a[j]) or (a[j] in m_2 and m_2[a[j]] != s[j]): 91 ok = False 92 break 93 print("YES" if ok else "NO") 94 95 t = int(input()) 96 for _ in range(t): 97 solve() 98 ``` 99 100 [2000D - Right Left Wrong](/contest/2000/problem/D "Codeforces Round 966 (Div. 3)") 101 102 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution** 109 110 ``` 111 def solve(): 112 n = int(input()) 113 a = [0] 114 for x in input().split(): 115 x = int(x) 116 a.append(a[-1] + x) 117 s = input() 118 ans = 0 119 l = 0 120 r = n - 1 121 while r > l: 122 while l < n and s[l] == 'R': 123 l += 1 124 while r >= 0 and s[r] == 'L': 125 r -= 1 126 if l < r: 127 ans += a[r + 1] - a[l] 128 l += 1 129 r -= 1 130 print(ans) 131 132 t = int(input()) 133 for _ in range(t): 134 solve() 135 ``` 136 137 [2000E - Photoshoot for Gorillas](/contest/2000/problem/E "Codeforces Round 966 (Div. 3)") 138 139 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 #define int long long 151 152 using namespace std; 153 154 #define MAXW 200200 155 #define MAXNM 200200 156 157 int n, m, k, w, p; 158 int arr[MAXW], prr[MAXNM]; 159 160 static inline int calcc(int i, int j) { 161 int upr = min(i, n - k); 162 int leftr = min(j, m - k); 163 int upl = max(-1LL, i - k); 164 int leftl = max(-1LL, j - k); 165 return (upr - upl) * (leftr - leftl); 166 } 167 168 void build() { 169 sort(arr, arr + w); 170 reverse(arr, arr + w); 171 p = 0; 172 for (int i = 0; i < n; ++i) 173 for (int j = 0; j < m; ++j) 174 prr[p++] = calcc(i, j); 175 sort(prr, prr + p); 176 reverse(prr, prr + p); 177 } 178 179 int solve() { 180 int sum = 0; 181 for (int i = 0; i < w; ++i) 182 sum += prr[i] * arr[i]; 183 return sum; 184 } 185 186 signed main() { 187 int t; cin >> t; 188 while (t--) { 189 cin >> n >> m >> k >> w; 190 for (int i = 0; i < w; ++i) 191 cin >> arr[i]; 192 build(); 193 cout << solve() << endl; 194 } 195 } 196 ``` 197 198 [2000F - Color Rows and Columns](/contest/2000/problem/F "Codeforces Round 966 (Div. 3)") 199 200 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy") 201 202 **Tutorial** 203 204 Tutorial is loading... 205 206 **Solution** 207 208 ``` 209 #include <iostream> 210 #include <algorithm> 211 #include <vector> 212 213 using namespace std; 214 215 void solve() { 216 int n, k; 217 cin >> n >> k; 218 vector<int> a(n), b(n); 219 for (int i = 0; i < n; ++i) { 220 cin >> a[i] >> b[i]; 221 } 222 vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1e9)); 223 dp[0][0] = 0; 224 for (int i = 0; i < n; ++i) { 225 int x = a[i], y = b[i]; 226 int xy = x + y; 227 int cost = 0; 228 for (int j = 0; j <= xy; ++j) { 229 for (int j1 = 0; j1 + j <= k; ++j1) { 230 dp[i + 1][j1 + j] = min(dp[i + 1][j1 + j], dp[i][j1] + cost); 231 } 232 if (j < xy) { 233 if (x >= y) { 234 x--, cost += y; 235 } else { 236 y--, cost += x; 237 } 238 } 239 } 240 } 241 cout << (dp[n][k] == 1e9 ? -1 : dp[n][k]) << '\n'; 242 } 243 244 int main() { 245 int t; 246 cin >> t; 247 for (int i = 0; i < t; ++i) { 248 solve(); 249 } 250 return 0; 251 } 252 ``` 253 254 [2000G - Call During the Journey](/contest/2000/problem/G "Codeforces Round 966 (Div. 3)") 255 256 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy") 257 258 **Tutorial** 259 260 Tutorial is loading... 261 262 **Solution** 263 264 ``` 265 #include <iostream> 266 #include <vector> 267 #include <set> 268 269 using namespace std; 270 271 void solve() { 272 int n, m; 273 cin >> n >> m; 274 int t0, t1, t2; 275 cin >> t0 >> t1 >> t2; 276 vector<vector<vector<int>>> g(n); 277 for (int i = 0; i < m; ++i) { 278 int u, v, l1, l2; 279 cin >> u >> v >> l1 >> l2; 280 u--, v--; 281 g[u].push_back({v, l1, l2}); 282 g[v].push_back({u, l1, l2}); 283 } 284 set<pair<int, int>> prq; 285 prq.insert({t0, n - 1}); 286 for (int i = 0; i + 1 < n; ++i) { 287 prq.insert({-1e9, i}); 288 } 289 vector<int> dist(n, -1e9); 290 dist[n - 1] = t0; 291 while (!prq.empty()) { 292 auto p = *prq.rbegin(); 293 prq.erase(p); 294 int d = p.first, u = p.second; 295 for (auto e: g[u]) { 296 int v = e[0], l1 = e[1], l2 = e[2]; 297 int d1 = (d - l1 >= t2 || d <= t1) ? d - l1 : d - l2; 298 if(d1 == d - l2) d1 = max(d1, t1 - l1); 299 if (dist[v] < d1) { 300 prq.erase({dist[v], v}); 301 dist[v] = d1; 302 prq.insert({d1, v}); 303 } 304 } 305 } 306 cout << (dist[0] >= 0 ? dist[0] : -1) << '\n'; 307 } 308 309 int main() { 310 int t; 311 cin >> t; 312 for (int i = 0; i < t; ++i) { 313 solve(); 314 } 315 return 0; 316 } 317 ``` 318 319 [2000H - Ksyusha and the Loaded Set](/contest/2000/problem/H "Codeforces Round 966 (Div. 3)") 320 321 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "International Master ibraevdmitriy") 322 323 **Tutorial** 324 325 Tutorial is loading... 326 327 **Solution** 328 329 ``` 330 #pragma GCC optimize("O3,unroll-loops") 331 332 #include <bits/stdc++.h> 333 334 #define endl '\n' 335 336 using namespace std; 337 338 typedef pair<int, int> ipair; 339 340 #define INF 1'000'000'009 341 #define MAXN 200200 342 #define MAXMEM 5'000'000 343 #define MAXLEN 2'000'100 344 345 #define X first 346 #define Y second 347 348 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 349 350 struct node { 351 node *lv = nullptr, *rv = nullptr; 352 ipair key; 353 int prior; 354 int minl = INF; 355 356 node(const ipair& key) : key(key), prior(rng()), minl(key.Y) {} 357 }; 358 359 static inline int minl(node *v) { 360 return (v == nullptr ? INF : v->minl); 361 } 362 363 static inline void upd(node *v) { 364 v->minl = min(v->key.Y, min(minl(v->lv), minl(v->rv))); 365 } 366 367 node *merge(node *s1, node *s2) { 368 if (s1 == nullptr) return s2; 369 if (s2 == nullptr) return s1; 370 if (s1->prior > s2->prior) { 371 s1->rv = merge(s1->rv, s2); 372 upd(s1); 373 return s1; 374 } else { 375 s2->lv = merge(s1, s2->lv); 376 upd(s2); 377 return s2; 378 } 379 } 380 381 pair<node*, node*> split(node* &v, ipair x) { 382 if (v == nullptr) { 383 return {nullptr, nullptr}; 384 } 385 if (v->key < x) { 386 auto [s1, s2] = split(v->rv, x); 387 v->rv = s1; 388 upd(v); 389 return {v, s2}; 390 } else { 391 auto [s1, s2] = split(v->lv, x); 392 v->lv = s2; 393 upd(v); 394 return {s1, v}; 395 } 396 } 397 398 int n, m; 399 int arr[MAXN]; 400 node *mem = (node*)calloc(MAXMEM, sizeof(*mem)); 401 node *mpos = mem; 402 node *root; 403 set<int> M; 404 405 // [l..r) 406 void add_seg(int l, int r) { 407 if (l >= r) return; 408 ipair p {r - l, l}; 409 auto [s1, s2] = split(root, p); 410 node *v = mpos++; 411 *v = node(p); 412 root = merge(merge(s1, v), s2); 413 } 414 415 void rem_dek(node* &v, const ipair& x) { 416 if (v == nullptr) return; 417 if (v->key == x) { 418 v = merge(v->lv, v->rv); 419 if (v) upd(v); 420 return; 421 } 422 if (v->key < x) rem_dek(v->rv, x); 423 else rem_dek(v->lv, x); 424 upd(v); 425 } 426 427 // [l..r) 428 void rem_seg(int l, int r) { 429 if (l >= r) return; 430 ipair p {r - l, l}; 431 rem_dek(root, p); 432 } 433 434 void add_val(int x) { 435 auto it = M.lower_bound(x); 436 int clsl = (it == M.begin() ? 0 : *prev(it)); 437 int clsr = (it == M.end() ? INF : *it); 438 rem_seg(clsl + 1, clsr); 439 add_seg(clsl + 1, x); 440 if (clsr != INF) add_seg(x + 1, clsr); 441 M.insert(x); 442 } 443 444 void rem_val(int x) { 445 auto it = M.lower_bound(x); 446 int clsl = (it == M.begin() ? 0 : *prev(it)); 447 int clsr = (next(it) == M.end() ? INF : *next(it)); 448 rem_seg(clsl + 1, x); 449 rem_seg(x + 1, clsr); 450 if (clsr != INF) add_seg(clsl + 1, clsr); 451 M.erase(x); 452 } 453 454 int query(int k) { 455 if (M.empty()) return 1; 456 auto [s1, s2] = split(root, make_pair(k, -1)); 457 fprintf(stderr, "AMOGUS: %p, %p\n", s1, s2); 458 int ans = min(*M.rbegin() + 1, minl(s2)); 459 root = merge(s1, s2); 460 return ans; 461 } 462 463 void init() { 464 root = nullptr; 465 mpos = mem; 466 M = {arr, arr + n}; 467 add_seg(1, *M.begin()); 468 for (auto it = M.begin(); next(it) != M.end(); ++it) 469 add_seg(*it + 1, *next(it)); 470 } 471 472 signed main() { 473 int t; cin >> t; 474 while (t--) { 475 cin >> n; 476 for (int i = 0; i < n; ++i) 477 cin >> arr[i]; 478 init(); 479 cin >> m; 480 for (int j = 0; j < m; ++j) { 481 char tp; cin >> tp; 482 int x, k; 483 switch (tp) { 484 case '+': 485 cin >> x; 486 add_val(x); 487 break; 488 case '-': 489 cin >> x; 490 rem_val(x); 491 break; 492 case '?': 493 cin >> k; 494 cout << query(k) << " "; 495 break; 496 } 497 } 498 cout << endl; 499 } 500 } 501 ```