2044.md (21815B)
1 Source: https://codeforces.com/blog/entry/137306 2 3 #### Special thanks to our hub of testuwuers for contributing solution explanations! 4 5 #### [2044A - Легкая задача](/contest/2044/problem/A "Codeforces Round 993 (Div. 4)") 6 7 Problem Credits: [cry](/profile/cry "Международный мастер cry") 8 Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev") 9 10 **Solution** 11 12 For any $n$, Cube can set $a$ = any integer between $1$ and $n-1$ inclusive, and set $b = n - a$. $a$ cannot be less than $1$, because then it would be non-positive, and $a$ cannot be greater than $n-1$, because then $b$ would be less than $1$, which would make it non-positive. Therefore the answer is just $n-1$ for all $n$. 13 14 **Code (Python)** 15 16 ``` 17 input = sys.stdin.readline 18 for _ in range(int(input())): 19 print(int(input())-1) 20 ``` 21 22 #### [2044B - Обычная задача](/contest/2044/problem/B "Codeforces Round 993 (Div. 4)") 23 24 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad") 25 Analysis: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad"), [macaquedev](/profile/macaquedev "Специалист macaquedev") 26 27 **Solution** 28 29 The letters she reads that comprise string $b$ are just the letters that comprise string $a$, flipped left-to-right. This means that 'p' becomes 'q', 'q' becomes 'p', and 'w' stays 'w', since it is vertically symmetrical. The order in which the letters are read is also reversed, because what used to be the left side of string $a$ gets flipped over to the right side of string $b$, and vice versa. 30 31 We now have an algorithm for constructing string $b$, which is to iterate from right-to-left on string $a$, outputting 'p' when there is a 'q', 'q' when there is a 'p', and 'w' when there is a 'w'. 32 33 **Code (C++)** 34 35 ``` 36 #include <bits/stdc++.h> 37 using namespace std; 38 #define ll long long 39 #define pll pair<ll, ll> 40 41 int t; 42 43 int main() { 44 cin.tie(0)->sync_with_stdio(0); 45 cin >> t; 46 while (t--) { 47 string s; 48 cin >> s; 49 reverse(s.begin(), s.end()); 50 for (char &c : s) if (c == 'q') c = 'p'; else if (c == 'p') c = 'q'; 51 cout << s << '\n'; 52 } 53 } 54 ``` 55 56 #### [2044C - Сложная задача](/contest/2044/problem/C "Codeforces Round 993 (Div. 4)") 57 58 Problem Credits: [cry](/profile/cry "Международный мастер cry") 59 Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev") 60 61 **Solution** 62 63 Let $A$, $B$, $C$ be three sets of monkeys, such that monkeys in $A$ can only sit in row $1$, $B$ in row $2$, and $C$ can sit anywhere. It is clear that if there is free space in row $1$, and there are monkeys left in set $A$, it is optimal to seat a monkey from set $A$ onto row $1$. This is because a monkey from set $C$ can be seated on either row, and there might be space left on the other row for that same monkey in set $C$ after you've already seated the monkey from set $A$. However, this is not the case if you start by seating the monkeys in set $C$ in the front row, since you might now leave empty seats at the back, but then have monkeys from set $A$ still left unseated. 64 65 Therefore, the strategy is as follows: seat as many monkeys from set $A$ as you can in the front row, then seat as many monkeys from set $B$ as you can in the back row, then seat as many monkeys from set $C$ as you can, and that yields the answer. 66 67 **Code (C++)** 68 69 ``` 70 #include<bits/stdc++.h> 71 #define ll long long 72 using namespace std; 73 74 int main() 75 { 76 ios::sync_with_stdio(false); 77 cin.tie(nullptr); 78 int tt; 79 cin>>tt; 80 while(tt--) 81 { 82 int m,a,b,c; 83 cin>>m>>a>>b>>c; 84 int ans=0,rem=0; 85 ans+=min(m,a);rem+=m-min(m,a); 86 ans+=min(m,b);rem+=m-min(m,b); 87 ans+=min(rem,c); 88 cout<<ans<<'\n'; 89 } 90 return 0; 91 } 92 ``` 93 94 #### [2044D - Задача посложнее](/contest/2044/problem/D "Codeforces Round 993 (Div. 4)") 95 96 Problem Credits: [cry](/profile/cry "Международный мастер cry"), [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED") 97 Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev") 98 99 **Solution** 100 101 Observe that if you have an array where all elements are unique, they will all have frequency $1$, therefore they can all be classified as the mode. Therefore, it follows that the strategy for the construction is to just construct an array where for each prefix, the last element of this prefix appears in the array at least once. An easy way of doing is this is such: 102 103 For each element $a_i$, if this value has appeared previously in the array (you can use a set to check this), set $b_i$ equal to some random integer that isn't used elsewhere in the list $a$, and keep going. Otherwise, set $b_i = a_i$. 104 105 **Code (C++)** 106 107 ``` 108 #include<bits/stdc++.h> 109 #define ll long long 110 using namespace std; 111 112 int main() 113 { 114 ios::sync_with_stdio(false); 115 cin.tie(nullptr); 116 int tt; 117 cin>>tt; 118 while(tt--) 119 { 120 int n; 121 cin>>n; 122 vector<int> a(n+1),b(n); 123 for(int i=0;i<n;i++) 124 { 125 int x; 126 cin>>x; 127 if(!a[x]) 128 { 129 b[i]=x; 130 a[x]=1; 131 } 132 } 133 queue<int> q; 134 for(int i=1;i<=n;i++) 135 if(!a[i]) 136 q.push(i); 137 for(int i=0;i<n;i++) 138 { 139 if(!b[i]) 140 { 141 b[i]=q.front(); 142 q.pop(); 143 } 144 } 145 for(int i=0;i<n;i++) 146 cout<<b[i]<<" \n"[i==n-1]; 147 } 148 return 0; 149 } 150 ``` 151 152 #### [2044E - Безумная задача](/contest/2044/problem/E "Codeforces Round 993 (Div. 4)") 153 154 Problem Credits: [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED"),[Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad") 155 Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev"), [chromate00](/profile/chromate00 "Эксперт chromate00") 156 157 **Solution 1 (Binary Search)** 158 159 Clearly, trying to bruteforce over all possible values of $x$ or $y$ is too slow, because the bounds are $1 \leq l_1 \leq r_1 \leq 10^9$. However, there is another variable that you can actually bruteforce over — and that is $n$. This is because exponentiation famously makes numbers very big very quickly — and if we set $k$ as small as possible (i.e. $2$), we only need to check $1 \leq n \leq 32$. This is because $2^{32} \gt 10^9$, so there cannot possibly be any solutions for $n \gt 32$ for any $k$. 160 161 Now, let's rephrase the problem. We need to find pairs $(x, y)$ such that $x \cdot k^n = y$. Now, we can check every value of $n$ from $1$ to $32$, and for each, binary search to find the smallest $x$ such that $y$ fits the conditions, and the largest $x$. Now, we can subtract these two values and add this to the answer. 162 163 **Solution 2 (Intervals)** 164 165 Note that we do not need to care about more than $32$ different values of $k^n$, because obviously $k^{32} \ge 2^{32} \gt 10^9$. From here and on, we focus on solving for only one value of $k^n$. 166 167 When $k^n$ is fixed and you are given $\frac{y}{x}=k^n$, notice $y$ is fixed as $x k^n$. Therefore, if we count the values $x$ such that $y$ is in the given interval as well, we will be properly counting the ordered pairs. 168 169 Formally, this condition can be cleared out as: 170 171 * $l_2 \le x k^n \le r_2$ 172 * $\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}$ 173 * Because $x$ is an integer, $\left \lceil {\frac{l_2}{k^n}} \right \rceil \le x \le \left \lfloor {\frac{r_2}{k^n}} \right \rfloor$ 174 175 Thus, when we intersect the two intervals, we get the following interval at last. 176 177 $\max \left({l_1,\left \lceil {\frac{l_2}{k^n}} \right \rceil}\right) \le x \le \min \left({r_1,\left \lfloor {\frac{r_2}{k^n}} \right \rfloor}\right)$ 178 179 Compute the size of this interval for all $k^n$ (at most $32$ values) and the answer can be found. 180 181 Do note the following details while implementing: 182 183 * When $r \lt l$, the size of the interval is $0$, not negative. 184 * Beware of overflows. Dealing with big integers can be helpful in avoiding this, but it may make your solution slow. 185 * Do not round up a fraction using the `ceil` function; This has been a recurring issue in almost every Div.4! 186 187 **Code (C++)** 188 189 ``` 190 #include<bits/stdc++.h> 191 #define ll long long 192 using namespace std; 193 194 int main() 195 { 196 ios::sync_with_stdio(false); 197 cin.tie(nullptr); 198 int tt; 199 cin>>tt; 200 while(tt--) 201 { 202 ll k,l1,r1,l2,r2; 203 cin>>k>>l1>>r1>>l2>>r2; 204 ll kn=1,ans=0; 205 for(int n=0;r2/kn>=l1;n++) 206 { 207 ans+=max(0ll,min(r2/kn,r1)-max((l2-1)/kn+1,l1)+1ll); 208 kn*=k; 209 } 210 cout<<ans<<'\n'; 211 } 212 return 0; 213 } 214 ``` 215 216 #### [2044F - Легкая демоническая задача](/contest/2044/problem/F "Codeforces Round 993 (Div. 4)") 217 218 Problem Credits: [chromate00](/profile/chromate00 "Эксперт chromate00"), [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED") 219 Analysis: [DivinePunishment](/profile/DivinePunishment "Эксперт DivinePunishment") 220 221 **Are you a python user and failing test 12?** 222 223 This is an anti-hash test for python sets and dictionaries. Before you call us evil, we saved you from getting hacked in open hack phase. Beware! 224 225 **Solution** 226 227 Let's denote the beauty of the matrix as $B$, and denote $\text{SumA}$ as the sum of all the elements in the array $a$, and $\text{SumB}$ as the sum of all the elements in the array $b$. 228 229 Before applying an operation, the beauty of the matrix can be expressed as: 230 231 $B = b_1 \cdot a_1 + b_1 \cdot a_2 + b_1 \cdot a_3 + b_2 \cdot a_1 + b_2 \cdot a_2 + \ldots$ 232 233 After factoring, this simplifies to: 234 235 $ B = b_1 \cdot (a_1 + a_2 + a_3 + \ldots) + b_2 \cdot (a_1 + a_2 + a_3 + \ldots) + \ldots $ 236 237 Further factoring gives: 238 239 $ B = (a_1 + a_2 + a_3 + a_4 + \ldots) \cdot (b_1 + b_2 + b_3 + \ldots) $ 240 241 This can be written as: 242 243 $ B = \text{SumA} \cdot \text{SumB}$ 244 245 Now, consider the effect of an operation on a column $C$. The beauty decreases by $A_c \cdot \text{SumB}$. Similarly, when an operation is done on a row $R$, the beauty decreases by $B_r \cdot \text{SumA}$. 246 247 An important observation is that the element at position $(r, c)$ is counted twice, so we must account for this in the formula. 248 249 After considering this, let the beauty after the operations be denoted as $X$. Using the observations above: 250 251 $X = B - (b_i \cdot \text{SumA} + a_j \cdot \text{SumB} - a_j \cdot b_i)$ 252 253 Simplifying further: 254 255 $X = \text{SumA} \cdot \text{SumB} - b_i \cdot \text{SumA} - a_j \cdot \text{SumB} + a_j \cdot b_i$ 256 257 Factoring terms, we obtain: 258 259 $X = \text{SumA} \cdot (\text{SumB} - b_i) - a_j \cdot (\text{SumB} - b_i)$ 260 261 Finally: 262 263 $X = (\text{SumB} - b_i) \cdot (\text{SumA} - a_j)$ 264 265 At this stage, it is sufficient to iterate over the divisors of $X$. For each ordered pair of divisors whose product is $X$, we check whether the required values of $\text{SumB} - b_i$ and $\text{SumA} - a_j$ can be achieved. 266 267 This can be implemented using a simple map or boolean vector for faster computation, although such optimization is not required for this problem. 268 269 **Code (C++)** 270 271 ``` 272 #include <bits/stdc++.h> 273 using namespace std; 274 #define FOR(i,a,b) for (int i = (a); i < (b); ++i) 275 #define F0R(i,a) FOR(i,0,a) 276 #define int long long 277 #define vt vector 278 #define endl "\n" 279 280 const int N = 4e5 + 5; 281 bool apos[N], aneg[N], bpos[N], bneg[N], posspos[N], possneg[N]; 282 283 signed main() { 284 ios_base::sync_with_stdio(false); 285 cin.tie(0); 286 int n,m,q; 287 cin >> n >> m >> q; 288 vector<int> a(n), b(m); 289 int asum = 0, bsum = 0; 290 F0R(i, n) { 291 cin >> a[i]; 292 asum += a[i]; 293 } 294 F0R(i, m) { 295 cin >> b[i]; 296 bsum += b[i]; 297 } 298 F0R(i, n) { 299 if(abs(asum-a[i]) < N) { 300 if(asum-a[i]<0) aneg[a[i]-asum]=true; 301 else apos[asum-a[i]]=true; 302 } 303 } 304 F0R(i, m) { 305 if(abs(bsum-b[i]) < N) { 306 if(bsum-b[i]<0) bneg[b[i]-bsum]=true; 307 else bpos[bsum-b[i]]=true; 308 } 309 } 310 FOR(i, 1, N) { 311 FOR(j, 1, N) { 312 if(i * j > N) break; 313 if(apos[i]&&bpos[j]) posspos[i*j]=true; 314 if(apos[i]&&bneg[j]) possneg[i*j]=true; 315 if(aneg[i]&&bpos[j]) possneg[i*j]=true; 316 if(aneg[i]&&bneg[j]) posspos[i*j]=true; 317 } 318 } 319 while(q--) { 320 int x; 321 cin >> x; 322 if(x>0) { 323 if(posspos[x]) { 324 cout << "YES" << endl; 325 } else { 326 cout << "NO" << endl; 327 } 328 } else { 329 if(possneg[-x]) { 330 cout << "YES" << endl; 331 } else { 332 cout << "NO" << endl; 333 } 334 } 335 } 336 return 0; 337 } 338 ``` 339 340 #### [2044G1 - Средняя демоническая задача (легкая версия)](/contest/2044/problem/G1 "Codeforces Round 993 (Div. 4)") 341 342 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad") 343 Analysis: [macaquedev](/profile/macaquedev "Специалист macaquedev") 344 345 **Solution** 346 347 This problem deals with a specific subclass of graphs called "functional graphs", also known as "successor graphs". The key feature that they have is that each node only has one successor. Therefore, the graph in the problem will necessarily be split into $k \geq 1$ components, where each component necessarily contains one cycle, and each node will either be in the cycle, or it will be on a path leading towards the cycle. 348 349 Observe that if a node that is not on a cycle currently has a plushie, this plushie will cause the arrangement to be unstable until the plushie reaches the cycle. Proof: suppose node $u$ has the plushie on day $i$. On the next day, $u$ will no longer have this plushie, because they will have passed it down to $r_u$, therefore, the arrangement has changed. This continues inductively until the plushie reaches the cycle of its component. 350 351 From this, we know that the answer is at least the distance of any node to the cycle. Now, since every node in the cycle already has a plushie, we know that these plushies just get passed round and round, so actually, nodes within the cycle cannot change the answer. Therefore, we've already found the final answer. 352 353 **Code (C++)** 354 355 ``` 356 #include<bits/stdc++.h> 357 #define ll long long 358 using namespace std; 359 360 int main() 361 { 362 ios::sync_with_stdio(false); 363 cin.tie(nullptr); 364 int tt; 365 cin>>tt; 366 while(tt--) 367 { 368 int n; 369 cin>>n; 370 vector<int> r(n+1),d(n+1); 371 for(int i=1;i<=n;i++) 372 { 373 cin>>r[i]; 374 d[r[i]]++; 375 } 376 set<pair<int,int> > s; 377 for(int i=1;i<=n;i++) 378 s.insert({d[i],i}); 379 int ans=2; 380 queue<int> q; 381 while(!s.empty()&&(*s.begin()).first==0) 382 { 383 while(!s.empty()&&(*s.begin()).first==0) 384 { 385 int k=(*s.begin()).second; 386 auto it=s.find({d[r[k]],r[k]}); 387 d[r[k]]--; 388 if(it!=s.end()) 389 { 390 s.erase(it); 391 q.push(r[k]); 392 } 393 s.erase(s.begin()); 394 } 395 while(!q.empty()) 396 s.insert({d[q.front()],q.front()}),q.pop(); 397 ans++; 398 } 399 cout<<ans<<'\n'; 400 } 401 return 0; 402 } 403 ``` 404 405 #### [2044G2 - Средняя демоническая задача (сложная версия)](/contest/2044/problem/G2 "Codeforces Round 993 (Div. 4)") 406 407 Problem Credits: [Lilypad](/profile/Lilypad "Кандидат в мастера Lilypad") 408 Analysis: [Proof_by_QED](/profile/Proof_by_QED "Международный мастер Proof_by_QED") 409 410 **Solution** 411 412 Note that similarly to G1, once all plushies end up in the hands of spiders who are in a loop, the process becomes stable. 413 414 Let's model the input as a collection of rooted forests. For each spider $i$, if $i$ is part of a loop, then let's compress the loop into a single node and use that as the root of a tree. Otherwise, if spider $i$ gives a present to spider $r_i$, then let's draw an edge from $i$ to $r_i$. Now, let $i$ be any node that is not part of a loop. How long will it take until spider $i$ runs out of presents? We can see that it is the subtree size of $i$, as one present leaves the subtree each year. 415 416 Thus, our challenge now is to process the nodes in an efficient order such that we can find the subtree size of all nodes. This can be done with topological sorting, which gives us an order that processes all nodes starting from the leaf upwards. After the topological sort, we may do dynamic programming to find subtree sizes of all nodes. Let $dp[i]$ be the number of days until spider $i$ runs out of presents. Let's suppose that we already calculated $dp[i]$ (we initialize it to be $1$ for all nodes since each spider starts with a present). Then, we should add $dp[i]$ to $dp[r_i]$. Doing this and adding up all $dp$ values of nodes directly before a cycle will yield the answer. 417 418 **Code (C++)** 419 420 ``` 421 #include<bits/stdc++.h> 422 #define ll long long 423 using namespace std; 424 425 int main() 426 { 427 ios::sync_with_stdio(false); 428 cin.tie(nullptr); 429 int tt; 430 cin>>tt; 431 while(tt--) 432 { 433 int n; 434 cin>>n; 435 vector<int> r(n+1),d(n+1),v(n+1,1); 436 for(int i=1;i<=n;i++) 437 { 438 cin>>r[i]; 439 d[r[i]]++; 440 } 441 set<pair<int,int> > s; 442 for(int i=1;i<=n;i++) 443 { 444 s.insert({d[i],i}); 445 } 446 int ans=2; 447 queue<int> q; 448 while(!s.empty()&&(*s.begin()).first==0) 449 { 450 while(!s.empty()&&(*s.begin()).first==0) 451 { 452 int k=(*s.begin()).second; 453 ans=max(ans,v[k]+2);v[r[k]]+=v[k]; 454 auto it=s.find({d[r[k]],r[k]}); 455 d[r[k]]--; 456 if(it!=s.end()) 457 { 458 s.erase(it); 459 q.push(r[k]); 460 } 461 s.erase(s.begin()); 462 } 463 while(!q.empty()) 464 s.insert({d[q.front()],q.front()}),q.pop(); 465 } 466 cout<<ans<<'\n'; 467 } 468 return 0; 469 } 470 ``` 471 472 #### [2044H - Сложная демоническая задача](/contest/2044/problem/H "Codeforces Round 993 (Div. 4)") 473 474 Problem Credits: [cry](/profile/cry "Международный мастер cry") 475 Analysis: [chromate00](/profile/chromate00 "Эксперт chromate00") 476 477 **Solution** 478 479 Consider translating the sum back onto the matrix. For simplicity we discuss about querying the whole matrix. 480 481 The sum we would like to find is $\sum_i i\cdot A_i$. Here, $A_i$ corresponds to $M_{(x,y)}$, so we will translate this to $\sum_{x,y} i\cdot M_{(x,y)}$. The issue left is on the $i$ multiplied to it. 482 483 Remember that we index the entries in increasing order of $y$, and then increasing order of $x$. Assuming $y$ and $x$ were $0$-indexed, this will mean entry $(x,y)$ corresponds to $x\cdot n + y$ (also $0$-indexed). You can notice that this naturally corresponds to the order we had defined as well. 484 485 Then, what we want to find is $\sum_{x,y} (x \cdot n + y + 1)\cdot M_{(x,y)}$. Notice $x \cdot n$, $y$, $1$ are independent, and we can split them into sums $\sum_x x \cdot n \cdot M_{(x,y)}$, $\sum_y y \cdot M_{(x,y)}$, $\sum M_{(x,y)}$. Each of these three sums can be precomputed entry by entry, and a 2D prefix sum can solve the answer for the entire matrix. 486 487 The query for a submatrix is very similar. Formally, you have to care about: 488 489 * That we have $y_2-y_1+1$ columns instead of $n$ now; 490 * That the precomputed values might not start from $0$ on the first row/column of the query. 491 492 Still, these two issues can be fixed using the three sums we have precomputed. The time complexity becomes $\mathcal{O}(n^2+q)$. 493 494 **Code (C++)** 495 496 ``` 497 #include <bits/stdc++.h> 498 using namespace std; 499 using ll = long long; 500 using vll = vector <ll>; 501 using ii = pair <ll, ll>; 502 using vii = vector <ii>; 503 504 void tc () { 505 ll n, Q; 506 cin >> n >> Q; 507 vector <vll> mat(n, vll(n)); 508 for (vll &ve : mat) { 509 for (ll &i : ve) cin >> i; 510 } 511 vector <vll> psR(n, vll(n+1)), psRr(n, vll(n+1)), psRc(n+1, vll(n+1)), ps(n+1, vll(n+1)), psRrc(n+1, vll(n+1)); 512 for (ll i = 0; i < n; i++) { 513 for (ll j = 0; j < n; j++) { 514 psR[i][j+1] = psR[i][j] + mat[i][j]; 515 } 516 } 517 for (ll i = 0; i < n; i++) { 518 for (ll j = 0; j < n; j++) { 519 psRr[i][j+1] = psRr[i][j] + mat[i][j]*(j+1); 520 } 521 } 522 for (ll i = 0; i < n; i++) { 523 for (ll j = 0; j <= n; j++) { 524 psRc[i+1][j] = psRc[i][j] + psR[i][j]*(i+1); 525 } 526 } 527 for (ll i = 0; i < n; i++) { 528 for (ll j = 0; j <= n; j++) { 529 psRrc[i+1][j] = psRrc[i][j] + psRr[i][j]; 530 } 531 } 532 for (ll i = 0; i < n; i++) { 533 for (ll j = 0; j <= n; j++) { 534 ps[i+1][j] = ps[i][j] + psR[i][j]; 535 } 536 } 537 while (Q--) { 538 ll x1, y1, x2, y2; 539 cin >> x1 >> y1 >> x2 >> y2; 540 x1--; y1--; x2--; y2--; 541 ll ans = 0; 542 ans += -(ps[x2+1][y2+1]-ps[x2+1][y1]-ps[x1][y2+1]+ps[x1][y1])*x1*(y2-y1+1); 543 ans += (psRc[x2+1][y2+1] - psRc[x1][y2+1] - (ps[x2+1][y2+1]-ps[x1][y2+1]))*(y2-y1+1); 544 545 ans += (psRc[x2+1][y1] - psRc[x1][y1] - (ps[x2+1][y1]-ps[x1][y1]))*-(y2-y1+1); 546 ans += (ps[x2+1][y2+1]-ps[x1][y2+1])*-y1; 547 ans += (ps[x2+1][y1]-ps[x1][y1])*y1; 548 549 ans += psRrc[x2+1][y2+1] - psRrc[x1][y2+1]; 550 ans +=-(psRrc[x2+1][y1] - psRrc[x1][y1]); 551 cout << ans << ' '; 552 } 553 cout << '\n'; 554 } 555 556 int main () { 557 cin.tie(nullptr) -> sync_with_stdio(false); 558 ll T; cin >> T; while (T--) { tc(); } 559 return 0; 560 } 561 ```