1635.md (7920B)
1 Source: https://codeforces.com/blog/entry/100153 2 3 [1635A - Min Or Sum](/contest/1635/problem/A "Codeforces Round 772 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 int main () { 16 ios::sync_with_stdio(false); 17 cin.tie(0); 18 int t; 19 cin >> t; 20 while (t--) { 21 int n; 22 cin >> n; 23 int ans = 0; 24 for (int i = 0, x; i < n; ++i) { 25 cin >> x; 26 ans |= x; 27 } 28 cout << ans << endl; 29 } 30 } 31 ``` 32 33 [1635B - Avoid Local Maximums](/contest/1635/problem/B "Codeforces Round 772 (Div. 2)") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution** 40 41 ``` 42 #include <bits/stdc++.h> 43 using namespace std; 44 45 int main () { 46 ios::sync_with_stdio(false); 47 cin.tie(0); 48 int t; 49 cin >> t; 50 while (t--) { 51 int n; 52 cin >> n; 53 vector <int> a(n); 54 for (int i = 0; i < n; ++i) { 55 cin >> a[i]; 56 } 57 int ans = 0; 58 for (int i = 1; i + 1 < n; ++i) { 59 if (a[i] > a[i - 1] && a[i] > a[i + 1]) { 60 if (i + 2 < n) { 61 a[i + 1] = max(a[i], a[i + 2]); 62 } else { 63 a[i + 1] = a[i]; 64 } 65 ans++; 66 } 67 } 68 cout << ans << endl; 69 for (int i = 0; i < n; ++i) { 70 cout << a[i] << " \n"[i == n - 1]; 71 } 72 } 73 } 74 ``` 75 76 [1635C - Differential Sorting](/contest/1635/problem/C "Codeforces Round 772 (Div. 2)") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution** 83 84 ``` 85 #include <bits/stdc++.h> 86 using namespace std; 87 88 int main () { 89 ios::sync_with_stdio(false); 90 cin.tie(0); 91 int t; 92 cin >> t; 93 while (t--) { 94 int n; 95 cin >> n; 96 vector <int> a(n); 97 for (int i = 0; i < n; ++i) { 98 cin >> a[i]; 99 } 100 if (a[n - 2] > a[n - 1]) { 101 cout << -1 << endl; 102 } else { 103 if (a[n - 1] < 0) { 104 if (is_sorted(a.begin(), a.end())) { 105 cout << 0 << endl; 106 } else { 107 cout << -1 << endl; 108 } 109 } else { 110 cout << n - 2 << endl; 111 for (int i = 1; i <= n - 2; ++i) { 112 cout << i << ' ' << n - 1 << ' ' << n << endl; 113 } 114 } 115 } 116 } 117 } 118 ``` 119 120 [1635D - Infinite Set](/contest/1635/problem/D "Codeforces Round 772 (Div. 2)") 121 122 **Tutorial** 123 124 Tutorial is loading... 125 126 **Solution** 127 128 ``` 129 #include <bits/stdc++.h> 130 using namespace std; 131 132 const int mod = 1e9 + 7; 133 134 int main () { 135 ios::sync_with_stdio(false); 136 cin.tie(0); 137 int n, p; 138 cin >> n >> p; 139 vector <int> a(n); 140 for (int i = 0; i < n; ++i) { 141 cin >> a[i]; 142 } 143 sort(a.begin(), a.end()); 144 set <int> useful; 145 for (int i = 0; i < n; ++i) { 146 int x = a[i]; 147 bool flag = false; 148 while (x > 0) { 149 if (useful.count(x)) { 150 flag = true; 151 } 152 if (x & 1) { 153 x >>= 1; 154 } else if (x & 3) { 155 break; 156 } else { 157 x >>= 2; 158 } 159 } 160 if (!flag) 161 useful.insert(a[i]); 162 } 163 vector <int> cnt(30, 0), dp(p); 164 for (int x : useful) { 165 cnt[__lg(x)]++; 166 } 167 int ans = 0; 168 for (int i = 0; i < p; ++i) { 169 if (i < 30) { 170 dp[i] = cnt[i]; 171 } 172 if (i >= 1) { 173 dp[i] += dp[i - 1]; 174 if (dp[i] >= mod) { 175 dp[i] -= mod; 176 } 177 } 178 if (i >= 2) { 179 dp[i] += dp[i - 2]; 180 if (dp[i] >= mod) { 181 dp[i] -= mod; 182 } 183 } 184 ans += dp[i]; 185 if (ans >= mod) { 186 ans -= mod; 187 } 188 } 189 cout << ans << endl; 190 } 191 ``` 192 193 [1635E - Cars](/contest/1635/problem/E "Codeforces Round 772 (Div. 2)") 194 195 **Tutorial** 196 197 Tutorial is loading... 198 199 **Solution** 200 201 ``` 202 #include <bits/stdc++.h> 203 using namespace std; 204 205 const int N = 200001; 206 207 struct edge { 208 int type, u, v; 209 }; 210 211 vector <int> adj[N]; 212 int col[N], topo[N]; 213 214 void dfs(int v) { 215 for (int u : adj[v]) if (col[u] == -1) { 216 col[u] = col[v] ^ 1; 217 dfs(u); 218 } 219 } 220 221 bool BipartiteColoring(int n) { 222 for (int i = 1; i <= n; ++i) 223 col[i] = -1; 224 for (int i = 1; i <= n; ++i) if (col[i] == -1) { 225 col[i] = 0; 226 dfs(i); 227 } 228 for (int i = 1; i <= n; ++i) for (int j : adj[i]) { 229 if (col[i] == col[j]) { 230 return false; 231 } 232 } 233 return true; 234 } 235 236 bool TopologicalSort(int n) { 237 vector <int> in(n + 1, 0); 238 for (int i = 1; i <= n; ++i) for (int j : adj[i]) { 239 in[j]++; 240 } 241 queue <int> q; 242 for (int i = 1; i <= n; ++i) if (in[i] == 0) { 243 q.push(i); 244 } 245 int ord = 0; 246 while (!q.empty()) { 247 int v = q.front(); q.pop(); 248 topo[v] = ord++; 249 for (int u : adj[v]) { 250 in[u]--; 251 if (in[u] == 0) { 252 q.push(u); 253 } 254 } 255 } 256 return ord == n; 257 } 258 259 int main () { 260 ios::sync_with_stdio(false); 261 cin.tie(0); 262 int n, m; 263 cin >> n >> m; 264 vector <edge> a(m); 265 for (int i = 0; i < m; ++i) { 266 cin >> a[i].type >> a[i].u >> a[i].v; 267 adj[a[i].u].push_back(a[i].v); 268 adj[a[i].v].push_back(a[i].u); 269 } 270 if (!BipartiteColoring(n)) { 271 cout << "NO" << endl; 272 return 0; 273 } 274 // col = 0 -> orient left, col = 1 -> orient right 275 for (int i = 1; i <= n; ++i) { 276 adj[i].clear(); 277 } 278 for (edge e : a) { 279 if (col[e.u] == 1) 280 swap(e.u, e.v); 281 if (e.type == 1) { 282 adj[e.u].push_back(e.v); 283 } else { 284 adj[e.v].push_back(e.u); 285 } 286 } 287 if (!TopologicalSort(n)) { 288 cout << "NO" << endl; 289 return 0; 290 } 291 cout << "YES" << endl; 292 for (int i = 1; i <= n; ++i) { 293 cout << (col[i] == 0 ? "L " : "R ") << topo[i] << endl; 294 } 295 } 296 ``` 297 298 [1635F - Closest Pair](/contest/1635/problem/F "Codeforces Round 772 (Div. 2)") 299 300 **Tutorial** 301 302 Tutorial is loading... 303 304 **Solution** 305 306 ``` 307 #include <bits/stdc++.h> 308 using namespace std; 309 310 const int N = 300005; 311 const long long INF = 1ll << 62; 312 313 vector <int> useful_pair[N]; 314 vector <pair <int, int>> queries[N]; 315 316 long long bit[N]; 317 318 void modify(int p, long long v) { 319 for (int i = p; i > 0; i -= i & (-i)) { 320 bit[i] = min(bit[i], v); 321 } 322 } 323 324 long long query(int p) { 325 long long ans = INF; 326 for (int i = p; i < N; i += i & (-i)) { 327 ans = min(ans, bit[i]); 328 } 329 return ans; 330 } 331 332 int main () { 333 ios::sync_with_stdio(false); 334 cin.tie(0); 335 int n, q; 336 cin >> n >> q; 337 vector <int> x(n), w(n); 338 for (int i = 0; i < n; ++i) { 339 cin >> x[i] >> w[i]; 340 } 341 for (int i = 0, l, r; i < q; ++i) { 342 cin >> l >> r, --l; 343 queries[r].emplace_back(l, i); 344 } 345 stack <int> stk; 346 for (int i = 0; i < n; ++i) { 347 while (!stk.empty() && w[stk.top()] > w[i]) { 348 stk.pop(); 349 } 350 if (!stk.empty()) { 351 int x = stk.top(); 352 useful_pair[i].push_back(x); 353 } 354 stk.push(i); 355 } 356 while (!stk.empty()) { 357 stk.pop(); 358 } 359 for (int i = n - 1; ~i; --i) { 360 while (!stk.empty() && w[stk.top()] > w[i]) { 361 stk.pop(); 362 } 363 if (!stk.empty()) { 364 int x = stk.top(); 365 useful_pair[x].push_back(i); 366 } 367 stk.push(i); 368 } 369 fill(bit, bit + N, INF); 370 vector <long long> ans(q); 371 for (int r = 1; r <= n; ++r) { 372 for (int l : useful_pair[r - 1]) { 373 long long val = 1ll * (x[r - 1] - x[l]) * (w[l] + w[r - 1]); 374 modify(l + 1, val); 375 } 376 for (auto [l, id] : queries[r]) { 377 ans[id] = query(l + 1); 378 } 379 } 380 for (int i = 0; i < q; ++i) { 381 cout << ans[i] << endl; 382 } 383 } 384 ```