390.md (15270B)
1 Source: https://codeforces.com/blog/entry/64453 2 3 *Since the original data has been lost during the dark days of Codeforces, no version of the editorial has been re-released, and I feel the round itself is quite educational, so I decided to give a try.* 4 5 ## [390A - Inna and Alarm Clock](/contest/390/problem/A "Codeforces Round 229 (Div. 2)") 6 7 **Approach** 8 9 The criterion shows that we can only use either vertical segments or horizontal segments. 10 Since there is no limit on the segments' length, we can see that it's always optimal to use a segment with infinite length (or may be known as a line). 11 12 We can see that the vertical line *x* = *a* will span through every alarm clocks standing at positions with x-coordinate being equal to *a*. In a similar manner, the horizontal line *y* = *b* will span through every alarm clocks standing at positions with y-coordinate being equal to *b*. 13 14 So, if we use vertical lines, the number of segments used will be the number of distinct values of x-coordinates found in the data. Similarly, the number of horizontal segments used will be the number of distinct values of y-coordinates found. 15 16 The process can be implemented by a counting array, or a map. 17 18 Time complexity:  for regular arrays, or  for maps. 19 20 **Solution 1 (Map)** 21 22 Submission link: [48214007](/contest/390/submission/48214007 "Submission 48214007 by AkiLotus") 23 24 **Source code in plain text** 25 26 ``` 27 #pragma GCC optimize("Ofast") 28 29 #include <bits/stdc++.h> 30 using namespace std; 31 32 #define endl '\n' 33 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 34 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 35 36 int main(int argc, char* argv[]) { 37 ios_base::sync_with_stdio(0); cin.tie(NULL); 38 39 int n; cin >> n; 40 41 map<int, int> cntx, cnty; 42 43 while (n--) { 44 int x, y; 45 cin >> x >> y; 46 cntx[x]++; cnty[y]++; 47 } 48 49 cout << min(cntx.size(), cnty.size()) << endl; 50 51 return 0; 52 } 53 ``` 54 55 **Solution 2 (Array)** 56 57 Submission link: [48213984](/contest/390/submission/48213984 "Submission 48213984 by AkiLotus") 58 59 **Source code in plain text** 60 61 ``` 62 #pragma GCC optimize("Ofast") 63 64 #include <bits/stdc++.h> 65 using namespace std; 66 67 #define endl '\n' 68 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 69 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 70 71 int main(int argc, char* argv[]) { 72 ios_base::sync_with_stdio(0); cin.tie(NULL); 73 74 int n; cin >> n; 75 76 vector<int> cntx(101, 0); 77 vector<int> cnty(101, 0); 78 79 while (n--) { 80 int x, y; 81 cin >> x >> y; 82 cntx[x]++; cnty[y]++; 83 } 84 85 int distinctx = 0, distincty = 0; 86 for (int i=0; i<101; i++) { 87 distinctx += (cntx[i] > 0); 88 distincty += (cnty[i] > 0); 89 } 90 91 cout << min(distinctx, distincty) << endl; 92 93 return 0; 94 } 95 ``` 96 97 ## [390B - Inna, Dima and Song](/contest/390/problem/B "Codeforces Round 229 (Div. 2)") 98 99 **Approach** 100 101 From the constraints given, for the *i*-th song, provided there exists corresponding *x**i* and *y**i* values, then the following inequality must hold: 2 ≤ *x**i* + *y**i* ≤ 2·*a**i*. 102 Thus, if any *b**i* is either lower than 2 or higher than 2·*a**i*, then no *x**i* and *y**i* can be found, thus, Sereja's joy will surely decrease by 1. 103 104 Amongst all pairs of  that *x**i* + *y**i* = *b**i*, the pair with the highest value of *x**i*·*y**i* will be one with the equal value of *x**i* = *y**i* (this can be proven by the famous AM-GM inequality). 105 Thus, if *b**i* is divisible by 2, we can easily pick . 106 Also, from this, we can see (either intuitively or with static proofs) that the lower the difference between *x**i* and *y**i* is, the higher the value *x**i*·*y**i* will be. Thus, in case *b**i* being odd, the most optimal pair will be  or  (the order doesn't matter here). 107 108 Time complexity: . 109 110 **Solution** 111 112 Submission link: [48212208](/contest/390/submission/48212208 "Submission 48212208 by AkiLotus") 113 114 **Source code in plain text** 115 116 ``` 117 #pragma GCC optimize("Ofast") 118 119 #include <bits/stdc++.h> 120 using namespace std; 121 122 #define endl '\n' 123 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 124 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 125 126 int main(int argc, char* argv[]) { 127 ios_base::sync_with_stdio(0); cin.tie(NULL); 128 129 int n; cin >> n; 130 131 vector<int> a(n), b(n); 132 for (auto &z: a) cin >> z; 133 for (auto &z: b) cin >> z; 134 135 long long Joy = 0; 136 for (int i=0; i<n; i++) { 137 if (b[i] < 2 || b[i] > a[i] * 2) {Joy--; continue;} 138 int x = b[i] / 2, y = b[i] - x; 139 Joy += 1LL * x * y; 140 } 141 cout << Joy << endl; 142 143 return 0; 144 } 145 ``` 146 147 ## [390C - Inna and Candy Boxes](/contest/390/problem/C "Codeforces Round 229 (Div. 2)") 148 149 **Approach** 150 151 The query content looks pretty confusing at first, to be honest. 152 Since *k* is static throughout a scenario, we can group the boxes into *k* groups, the *z*-th box (in this editorial let's assume that the indices of the boxes start from 0) falls into group number . 153 154 Then, each query can be simplified as this: "Is that true that among the boxes with numbers from *l**i* to *r**i*, inclusive, the candies lie **only** in boxes of group ? 155 156 To make sure the answer for a query being "Yes", Dima has to remove candies from all candied-box in all groups other than , while in that exact group, fill every empty box with a candy. Obviously, we'll consider boxes with indices between *l**i* and *r**i* inclusively only. 157 158 We can make *k* lists, the *t*-th (0-indexed) list stores the indices of candied boxes in group *t*. 159 160 We'll process with each query as the following: 161 162 * Obviously, given from the criteria, each range will consist of exactly  boxes per each group. Let's denote . 163 * Traverse all groups, for the *t*-th group (again, 0-indexed), let's denote *x**t* as the number of candied boxes of group *t* in the given range. This value can be calculated quickly through binary searching the constructed lists above. 164 * If group *t* is not the group being demanded to have candies (group ), we'll need to perform *x**t* actions (removing candies). Otherwise, we'll need to perform *A* - *x**t* actions (adding candies to empty boxes). 165 166 Time complexity: . 167 168 **Solution** 169 170 Submission link: [48213932](/contest/390/submission/48213932 "Submission 48213932 by AkiLotus") 171 172 **Source code in plain text** 173 174 ``` 175 #pragma GCC optimize("Ofast") 176 177 #include <bits/stdc++.h> 178 using namespace std; 179 180 #define endl '\n' 181 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 182 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 183 184 int main(int argc, char* argv[]) { 185 ios_base::sync_with_stdio(0); cin.tie(NULL); 186 187 int n, k, w; string s; 188 cin >> n >> k >> w >> s; 189 190 vector< vector<int> > CandyGrp(k); 191 192 for (int i=0; i<n; i++) { 193 if (s[i] == '0') continue; 194 CandyGrp[i % k].push_back(i); 195 } 196 197 while (w--) { 198 int l, r; 199 cin >> l >> r; l--; r--; 200 201 int res = 0; 202 int demandedGroup = (l + k - 1) % k; 203 int BoxesPerGroup = (r - l + 1) / k; 204 205 for (int id=0; id<k; id++) { 206 207 int x = lower_bound(CandyGrp[id].begin(), CandyGrp[id].end(), l) - CandyGrp[id].begin(); 208 int y = upper_bound(CandyGrp[id].begin(), CandyGrp[id].end(), r) - CandyGrp[id].begin(); 209 210 if (id == demandedGroup) { 211 res += (BoxesPerGroup - (y - x)); 212 } 213 else res += (y - x); 214 } 215 216 cout << res << endl; 217 } 218 219 return 0; 220 } 221 ``` 222 223 ## [390D - Inna and Sweet Matrix](/contest/390/problem/D "Codeforces Round 229 (Div. 2)") 224 225 **Approach** 226 227 We can see that the most optimal placement will be choosing *k* cells being nearest to cell (1, 1) (yup, including (1, 1) itself). 228 To find these *k* points, we can simply do a BFS starting from (1, 1), with traceback feature to construct the paths to get to those cells. 229 However, keep in mind that any cell being candied will later on become obstacles for the following paths. Thus, to avoid blocking yourself, you should transfer candies to the farthest cells first, then getting closer. Thus, cell (1, 1) will be the last one being filled with candy. 230 231 Time complexity:  or , based on implementation (I myself did , since the difference isn't too much). 232 233 **Solution** 234 235 Submission link: [48213856](/contest/390/submission/48213856 "Submission 48213856 by AkiLotus") 236 237 **Source code in plain text** 238 239 ``` 240 #pragma GCC optimize("Ofast") 241 242 #include <bits/stdc++.h> 243 using namespace std; 244 245 #define endl '\n' 246 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 247 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 248 249 int dx[] = {-1, +0, +0, +1}; 250 int dy[] = {+0, -1, +1, +0}; 251 pair<int, int> Default = {-1, -1}; 252 253 int main(int argc, char* argv[]) { 254 ios_base::sync_with_stdio(0); cin.tie(NULL); 255 256 int n, m, k; cin >> n >> m >> k; 257 258 vector<vector<int>> Dist(n+2, vector<int>(m+2, 4444)); 259 vector<vector<pair<int, int>>> Last(n+2, vector<pair<int, int>>(m+2, Default)); 260 261 stack<pair<int, int>> Cells; 262 int cost = 0; 263 264 queue<pair<int, int>> Q; 265 Q.push({1, 1}); Dist[1][1] = 1; 266 267 while (!Q.empty() && Cells.size() < k) { 268 pair<int, int> C = Q.front(); Q.pop(); 269 Cells.push(C); int x = C.first, y = C.second; 270 271 cost += Dist[x][y]; 272 273 for (int dir=0; dir<4; dir++) { 274 if (x + dx[dir] < 1 || x + dx[dir] > n) continue; 275 if (y + dy[dir] < 1 || y + dy[dir] > m) continue; 276 277 if (Dist[x+dx[dir]][y+dy[dir]] != 4444) continue; 278 279 Dist[x+dx[dir]][y+dy[dir]] = Dist[x][y] + 1; 280 Q.push({x + dx[dir], y + dy[dir]}); 281 Last[x+dx[dir]][y+dy[dir]] = C; 282 } 283 } 284 285 cout << cost << endl; 286 287 while (!Cells.empty()) { 288 int x = Cells.top().first, y = Cells.top().second; Cells.pop(); 289 stack<pair<int, int>> Traceback; 290 291 while (x != -1 && y != -1) { 292 Traceback.push({x, y}); 293 pair<int, int> NextCell = Last[x][y]; 294 x = NextCell.first; y = NextCell.second; 295 } 296 297 while (!Traceback.empty()) { 298 pair<int, int> CurCell = Traceback.top(); 299 Traceback.pop(); 300 cout << "(" << CurCell.first << ", " << CurCell.second << ") "; 301 } 302 cout << endl; 303 } 304 305 return 0; 306 } 307 ``` 308 309 ## [390E - Inna and Large Sweet Matrix](/contest/390/problem/E "Codeforces Round 229 (Div. 2)") 310 311 **Approach** 312 313 Let's denote *A* as the total number of candies on the board, *R**i* as the total number of candies on the *i*-th row (1 ≤ *i* ≤ *n*), *C**j* as the total number of candies on the *j*-th column (1 ≤ *j* ≤ *m*). 314 315 Also, let's denote  and . 316 317 Let's considered the 2nd type of query first. Denoting the answer for the query as *f*(*x*1, *y*1, *x*2, *y*2), we can see that *f*(*x*1, *y*1, *x*2, *y*2) = *R*(*x*1, *x*2) + *C*(*y*1, *y*2) - *A* (you can draw a simple diagram and validate this function). 318 319 Thus, the problem is now reduced to calculating *R*(*x*1, *x*2), *C*(*y*1, *y*2) and *A*: 320 321 * *A* can be easily calculated. After each query of the 1st type with parameters *x*1, *y*1, *x*2, *y*2, *v*; *A* will be increased by *v*·(*x*2 - *x*1 + 1)·(*y*2 - *y*1 + 1). 322 * The calculation of *R*(*x*1, *x*2) and *C*(*y*1, *y*2) makes us thinking about some kinds of data structures that support range sum update and range sum query. Segment trees and Fenwick trees can both work on that. Personally I used segment trees, they fit in just right for the memory limit (I implemented it by vectors, regular arrays will obviously be safer). 323 324 Time complexity: . 325 326 **Solution** 327 328 Submission link: [48213830](/contest/390/submission/48213830 "Submission 48213830 by AkiLotus") 329 330 **Source code in plain text** 331 332 ``` 333 #pragma GCC optimize("Ofast") 334 335 #include <bits/stdc++.h> 336 using namespace std; 337 338 #define endl '\n' 339 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()); 340 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count()); 341 342 struct SegTree_Sum { 343 int n; vector<long long> Tree, Lazy; 344 SegTree_Sum() {} 345 SegTree_Sum(int _n) { 346 n = _n; 347 Tree.resize(n*4); 348 Lazy.resize(n*4); 349 } 350 351 void Propagate(int node, int st, int en) { 352 if (Lazy[node] == 0) return; 353 Tree[node] += Lazy[node] * (en - st + 1); 354 if (st != en) { 355 Lazy[node*2+1] += Lazy[node]; 356 Lazy[node*2+2] += Lazy[node]; 357 } 358 Lazy[node] = 0; 359 } 360 361 void Update(int node, int st, int en, int L, int R, long long val) { 362 Propagate(node, st, en); 363 if (en < st || R < st || en < L) return; 364 if (L <= st && en <= R) { 365 Lazy[node] += val; 366 Propagate(node, st, en); return; 367 } 368 Update(node*2+1, st, (st+en)/2+0, L, R, val); 369 Update(node*2+2, (st+en)/2+1, en, L, R, val); 370 Tree[node] = Tree[node*2+1] + Tree[node*2+2]; 371 } 372 373 long long Sum(int node, int st, int en, int L, int R) { 374 Propagate(node, st, en); 375 if (en < st || R < st || en < L) return 0LL; 376 if (L <= st && en <= R) return Tree[node]; 377 long long p1 = Sum(node*2+1, st, (st+en)/2+0, L, R); 378 long long p2 = Sum(node*2+2, (st+en)/2+1, en, L, R); 379 return (p1 + p2); 380 } 381 382 void RangeUpdate(int L, int R, long long val) { 383 Update(0, 0, n-1, L, R, val); 384 } 385 386 long long RangeSum(int L, int R) { 387 return Sum(0, 0, n-1, L, R); 388 } 389 }; 390 391 int main(int argc, char* argv[]) { 392 ios_base::sync_with_stdio(0); cin.tie(NULL); 393 394 int n, m, w; cin >> n >> m >> w; 395 396 long long TotalCandies = 0; 397 398 SegTree_Sum TreeRow = SegTree_Sum(n); 399 SegTree_Sum TreeCol = SegTree_Sum(m); 400 401 while (w--) { 402 int t, x1, y1, x2, y2; 403 cin >> t >> x1 >> y1 >> x2 >> y2; 404 405 if (t == 0) { 406 int v; cin >> v; 407 408 TotalCandies += 1LL * (x2 - x1 + 1) * (y2 - y1 + 1) * v; 409 410 TreeRow.RangeUpdate(x1, x2, 1LL * v * (y2 - y1 + 1)); 411 TreeCol.RangeUpdate(y1, y2, 1LL * v * (x2 - x1 + 1)); 412 } 413 else if (t == 1) { 414 long long res = 0; 415 416 res += TreeRow.RangeSum(x1, x2); 417 res += TreeCol.RangeSum(y1, y2); 418 res -= TotalCandies; 419 420 cout << res << endl; 421 } 422 } 423 424 return 0; 425 } 426 ```