689.md (20874B)
1 Source: https://codeforces.com/blog/entry/45912 2 3 [A.Mike and Cellphone](//codeforces.com/contest/689/problem/A) 4 5 Author:[danilka.pro](/profile/danilka.pro "International Master danilka.pro"). 6 7 Developed:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina"),[ThatMathGuy](/profile/ThatMathGuy "Candidate Master ThatMathGuy") 8 9 We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES". 10 11 **C++ code** 12 13 ``` 14 pair < int , int > s[55][55]; 15 int v[55][55]; 16 pair < int , int > where[55]; 17 int main(void) 18 { 19 for (int i = 1;i <= 10;++i) 20 for (int j = 1;j <= 10;++j) 21 v[i][j] = -1; 22 v[1][1] = 1; 23 v[1][2] = 2; 24 v[1][3] = 3; 25 v[2][1] = 4; 26 v[2][2] = 5; 27 v[2][3] = 6; 28 v[3][1] = 7; 29 v[3][2] = 8; 30 v[3][3] = 9; 31 v[4][2] = 0; 32 for (int k = 0;k <= 9;++k) 33 for (int i = 1;i <= 4;++i) 34 for (int j = 1;j <= 4;++j) 35 if (v[i][j] == k) where[k] = {i,j}; 36 for (int i = 0;i <= 9;++i) 37 for (int j = 0;j <= 9;++j) 38 s[i][j] = {where[i].x - where[j].x,where[i].y - where[j].y}; 39 string number; 40 int len; 41 fi>>len; 42 fi>>number; 43 vector < string > ans; 44 for (int k = 0;k <= 9;++k) 45 if (k != number[0] - '0') 46 { 47 string cnt = ""; 48 cnt += k + '0'; 49 auto pos = where[k]; 50 for (int i = 0;i < len - 1;++i) 51 { 52 pos.x += s[number[i+1] - '0'][number[i] - '0'].x; 53 pos.y += s[number[i+1] - '0'][number[i] - '0'].y; 54 if (1 <= pos.x && pos.x <= 4 && 1 <= pos.y && pos.y <= 3 && v[pos.x][pos.y] != -1) 55 cnt += v[pos.x][pos.y] + '0'; 56 else break; 57 } 58 if (cnt.length() == len) 59 { 60 fo << "NO\n"; 61 return 0; 62 } 63 } 64 puts("YES"); 65 return 0; 66 } 67 ``` 68 69 **Another C++ code** 70 71 ``` 72 pair<int, int> pos[10]; 73 int n; 74 char a[100]; pair<int, int> v[100]; 75 pair<int, int> operator - (pair<int, int> a, pair<int, int> b){ 76 return mp(a.first - b.first, a.second - b.second); 77 } 78 pair<int, int> operator + (pair<int, int> a, pair<int, int> b){ 79 return mp(a.first + b.first, a.second + b.second); 80 } 81 bool inside(pair<int, int> pos){ 82 return (pos.first <= 3 && 1 <= pos.first && pos.second <= 3 && pos.second >= 1) || pos == (mp(4, 2)); 83 } 84 int main(){ 85 int cnt = 0; 86 FOR(x, 1, 3){ 87 FOR(y, 1, 3){ 88 cnt++; 89 pos[cnt] = mp(x, y); 90 } 91 } 92 pos[0] = mp(4, 2); 93 cin >> n; 94 scanf("%s", a+1); 95 FOR(i, 1, n-1){ 96 v[i] = pos[a[i+1] - '0'] - pos[a[i] - '0']; 97 } 98 if(n == 1) return cout << "NO", 0; 99 int c = 0; 100 FOR(i, 0, 9){ 101 bool ok = true; 102 pair<int, int> curr_pos = pos[i]; 103 FOR(i, 1, n-1){ 104 curr_pos = curr_pos + v[i]; 105 if(!inside(curr_pos)) ok = false; 106 } 107 if(ok) c++; 108 } 109 if(c == 1) return cout << "YES", 0; 110 cout << "NO"; 111 } 112 ``` 113 114 **Another C++ code** 115 116 ``` 117 #include<bits/stdc++.h> 118 using namespace std; 119 typedef long long ll; 120 121 bool mark[11]; 122 bool flag1,flag2; 123 124 int main() 125 { 126 ll n; 127 string s; 128 cin>>n; 129 cin>>s; 130 for(int i=0;i<n;i++){ 131 mark[s[i]-'0']=true; 132 } 133 if((mark[1]||mark[2]||mark[3])&&(mark[7]||mark[9])) 134 flag1=true; 135 if((mark[1]||mark[4]||mark[7])&&(mark[3]||mark[6]||mark[9])) 136 flag2=true; 137 if((mark[1]||mark[2]||mark[3])&&mark[0]){ 138 cout<<"YES"; 139 return 0; 140 } 141 if(flag1&&flag2){ 142 cout<<"YES"; 143 return 0; 144 } 145 cout<<"NO"; 146 return 0; 147 } 148 ``` 149 150 **Python code** 151 152 ``` 153 n = int(raw_input()) 154 s = raw_input() 155 a = [] 156 for i in range(10): 157 a.append(True) 158 for i in range(n): 159 c = int(s[i]) 160 a[c] = False 161 inc = 0 162 if a[1] and a[2] and a[3]: 163 inc = -3 164 if a[7] and a[9] and a[0]: 165 inc = +3 166 if a[1] and a[4] and a[7] and a[0]: 167 inc = -1 168 if a[3] and a[6] and a[9] and a[0]: 169 inc = +1 170 if inc == 0: 171 print("YES") 172 else: 173 print("NO") 174 ``` 175 176 [B. Mike and Shortcuts](//codeforces.com/contest/689/problem/B) 177 178 Author:[danilka.pro](/profile/danilka.pro "International Master danilka.pro"),[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina") 179 180 Developed:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina"),[ThatMathGuy](/profile/ThatMathGuy "Candidate Master ThatMathGuy") 181 182 We can build a complete graph where the cost of going from point *i* to point *j* if |*i* - *j*| if *a**i*! = *j* and 1 if *a**i* = *j*.The we can find the shortest path from point 1 to point *i*.One optimisation is using the fact that there is no need to go from point *i* to point *j* if *j* ≠ *s*[*i*],*j* ≠ *i* - 1,*j* ≠ *i* + 1 so we can add only edges (*i*, *i* + 1),(*i*, *i* - 1),(*i*, *s*[*i*]) with cost 1 and then run a bfs to find the shortest path for each point *i*. 183 184 You can also solve the problem by taking the best answer from left and from the right and because *a**i* ≤ *a**i* + 1 then we can just iterate for each *i* form 1 to *n* and get the best answer from left and maintain a deque with best answer from right. 185 186 Complexity is *O*(*N*). 187 188 **C++ code with queue** 189 190 ``` 191 int d[1 << 20]; 192 int s[1 << 20]; 193 queue < int > Q; 194 void go(int k,int val) 195 { 196 if (d[k]) return; 197 d[k] = val; 198 Q.push(k); 199 } 200 int main(void) 201 { 202 int n; 203 scan(n);//scan integer 204 for (int i = 1;i <= n;++i) scan(s[i]); 205 go(1,1); 206 while (!Q.empty()) 207 { 208 int node = Q.front(); 209 Q.pop(); 210 go(s[node],d[node] + 1); 211 if (node > 1) go(node - 1,d[node] + 1); 212 if (node < n) go(node + 1,d[node] + 1); 213 } 214 for (int i = 1;i <= n;++i) print(d[i] - 1); 215 eol; 216 return 0; 217 } 218 ``` 219 220 **C++ code with deque** 221 222 ``` 223 #include <bits/stdc++.h> 224 using namespace std; 225 226 const int N = int(1e6) + 5; 227 int n, d[N], a[N], bd[N]; 228 229 int main() { 230 assert(cin >> n); 231 for (int i = 0; i < n; ++i) { 232 assert(scanf("%d", &a[i]) == 1); 233 a[i]--; 234 d[i] = i; 235 } 236 237 for (int i = 0; i < n; ++i) 238 bd[i] = int(1e9); 239 240 deque <int> st; 241 242 for (int i = 0; i < n; ++i) { 243 if (i) 244 d[i] = min(d[i], d[i - 1] + 1); 245 246 while (!st.empty() && st.front() < i) 247 st.pop_front(); 248 249 if (!st.empty()) 250 d[i] = min(d[i], bd[st.front()] - i); 251 252 d[a[i]] = min(d[a[i]], d[i] + 1); 253 bd[a[i]] = a[i] + d[a[i]]; 254 255 while (!st.empty() && bd[a[i]] <= bd[st.back()]) 256 st.pop_back(); 257 258 st.push_back(a[i]); 259 } 260 261 for (int i = 0; i < n; ++i) { 262 if (i) 263 putchar(' '); 264 printf("%d", d[i]); 265 } 266 return 0; 267 } 268 ``` 269 270 **Python code** 271 272 ``` 273 import Queue 274 n = int(raw_input()) 275 a = raw_input().split(' ') 276 used = [] 277 d = [] 278 for i in range(0, n): 279 used.append(False) 280 d.append(-1) 281 q = Queue.Queue() 282 q.put(0) 283 d[0] = 0 284 while not(q.empty()): 285 v = q.get() 286 for dl in range(-1, +2): 287 u = v + dl 288 if 0 <= u and u < n and d[u] == -1: 289 d[u] = d[v] + 1 290 q.put(u) 291 u = int(a[v]) - 1 292 if d[u] == -1: 293 d[u] = d[v] + 1 294 q.put(u) 295 for i in range(0, n): 296 print(d[i]) 297 ``` 298 299  What if you have *Q* queries *Q* ≤ 2 × 105 of type (*x**i*, *y**i*) and you have to answer the minimal distance from *x**i* to *y**i*. 300 301 [C. Mike and Chocolate Thieves](//codeforces.com/contest/689/problem/C) 302 303 Author:[danilka.pro](/profile/danilka.pro "International Master danilka.pro"),[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina") 304 305 Developed:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina"),[ThatMathGuy](/profile/ThatMathGuy "Candidate Master ThatMathGuy") 306 307 Suppose we want to find the number of ways for a fixed *n*. 308 309 Let *a*, *b*, *c*, *d* ( 0 < *a* < *b* < *c* < *d* ≤ *n* ) be the number of chocolates the thieves stole. By our condition, they have the form *b* = *ak*, *c* = *ak*2, *d* = *ak*3,where *k* is a positive integer. We can notice that  , so for each *k* we can count how many *a* satisfy the conditions 0 < *a* < *ak* < *ak*2 < *ak*3 ≤ *n*, their number is . Considering this, the final answer is . 310 311 Notice that this expression is non-decreasing as *n* grows, so we can run a binary search for *n*. 312 313 Total complexity: Time ~ , Space: *O*(1). 314 315 **C++ code** 316 317 ``` 318 ll get(ll x) 319 { 320 ll ans = 0; 321 for (int i = 2;1ll * i * i * i <= x;++i) 322 ans += x / (1ll * i * i * i); 323 return ans; 324 } 325 int main(void) 326 { 327 ll m; 328 fi>>m; 329 ll n = 0; 330 for (ll k = 1ll << 60;k;k /= 2) 331 if (n + k <= 1e16 && get(n+k) < m) n += k; 332 ++n; 333 if (get(n) == m) fo << n << '\n'; 334 else fo << "-1\n"; 335 return 0; 336 } 337 ``` 338 339 **Another C++ code** 340 341 ``` 342 # include <bits/stdc++.h> 343 using namespace std; 344 345 long long get(long long n) 346 { 347 long long ans = 0; 348 for (long long i = 2; i * i * i <= n;++i) 349 ans += n / (1ll*i * i * i); 350 return ans; 351 } 352 353 int main() 354 { 355 long long m,n=-1; 356 cin>>m; 357 358 long long l=0,r=5e15; 359 while (l<r) 360 { 361 long long mid = (l+r)/2; 362 if (get(mid)<m) l=mid+1; 363 else r=mid; 364 } 365 366 if (get(l)==m) n=l; 367 368 cout << n << '\n'; 369 return 0; 370 } 371 ``` 372 373 [D. Friends and Subsequences](//codeforces.com/contest/689/problem/D) 374 375 Author:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina") 376 377 Developed:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina"),[ThatMathGuy](/profile/ThatMathGuy "Candidate Master ThatMathGuy") 378 379 First of all it is easy to see that if we fix *l* then have . So we can just use binary search to find the smallest index *r**min* and biggest index *r**max* that satisfy the equality and add *r**max* - *r**min* + 1 to our answer. To find the *min* and *max* values on a segment [*l*, *r*] we can use Range-Minimum Query data structure. 380 381 The complexity is  time and  space. 382 383 **C++ code O(N)** 384 385 ``` 386 #include <bits/stdc++.h> 387 using namespace std; 388 389 int n, a[200001], b[200001]; 390 long long ans; 391 deque<int> mx, mn; 392 int main() { 393 scanf("%d",&n); 394 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 395 for(int i = 1; i <= n; i++) scanf("%d", &b[i]); 396 for(int i = 1, j = 1; i <= n; i++) { 397 while(!mx.empty() and a[mx.back()] <= a[i]) mx.pop_back(); 398 while(!mn.empty() and b[mn.back()] >= b[i]) mn.pop_back(); 399 mx.push_back(i); 400 mn.push_back(i); 401 while(j <= i and a[mx.front()] - b[mn.front()] > 0) { 402 j++; 403 while(!mx.empty() and mx.front() < j) mx.pop_front(); 404 while(!mn.empty() and mn.front() < j) mn.pop_front(); 405 } 406 if(!mx.empty() and !mn.empty() and a[mx.front()] == b[mn.front()]) ans += min(mx.front(), mn.front()) - j + 1; 407 } 408 printf("%lld", ans); 409 } 410 ``` 411 412 **C++ code O(N log N)** 413 414 ``` 415 # include <bits/stdc++.h> 416 # define scan(x) scanf("%d",&x) 417 using namespace std; 418 # define fi cin 419 # define fo cout 420 int dx[20][1 << 20]; 421 int dy[20][1 << 20]; 422 int lg[1 << 20]; 423 int mx(int l,int r) 424 { 425 int p = lg[r - l + 1]; 426 return max(dx[p][l],dx[p][r - (1 << p) + 1]); 427 } 428 int mn(int l,int r) 429 { 430 int p = lg[r - l + 1]; 431 return min(dy[p][l],dy[p][r - (1 << p) + 1]); 432 } 433 int main(void) 434 { 435 int n; 436 scan(n); 437 for (int i = 1;i <= n;++i) scan(dx[0][i]); 438 for (int i = 1;i <= n;++i) scan(dy[0][i]); 439 for (int p = 1;(1 << p) <= n;++p) 440 for (int i = 1;i + (1 << p) - 1 <= n;++i) 441 dx[p][i] = max(dx[p-1][i],dx[p-1][i + (1 << (p-1))]), 442 dy[p][i] = min(dy[p-1][i],dy[p-1][i + (1 << (p-1))]); 443 for (int i = 2;i <= n;++i) 444 lg[i] = lg[i >> 1] + 1; 445 long long ans = 0; 446 for (int i = 1;i <= n;++i) 447 if (mx(i,i) <= mn(i,i)) 448 { 449 int l = i-1,r = i; 450 for (int p = 1 << lg[n - i + 1];p;p >>= 1) 451 { 452 if (p + l <= n && mx(i,l+p) < mn(i,l+p)) l += p; 453 if (p + r <= n && mx(i,r+p) <= mn(i,r+p)) r += p; 454 } 455 ans += r - l; 456 } 457 fo << ans << '\n'; 458 } 459 ``` 460 461 **C++ code O(N log ^ 2 N)** 462 463 ``` 464 int a[1 << 20]; 465 int b[1 << 20]; 466 int Sa[1 << 20]; 467 int Sb[1 << 20]; 468 int n; 469 int lg[1 << 20]; 470 void updA(int i,int val) 471 { 472 for (;i <= n;i += i&(-i)) Sa[i] = max(Sa[i],val); 473 } 474 int quA(int i) 475 { 476 int ans = -(1e9+1); 477 for (;i;i -= i&(-i)) ans = max(ans,Sa[i]); 478 return ans; 479 } 480 void updB(int i,int val) 481 { 482 for (;i <= n;i += i&(-i)) Sb[i] = min(Sb[i],val); 483 } 484 int quB(int i) 485 { 486 int ans = (1e9+1); 487 for (;i;i -= i&(-i)) ans = min(ans,Sb[i]); 488 return ans; 489 } 490 int mx(int T) 491 { 492 return quA(T); 493 } 494 int mn(int T) 495 { 496 return quB(T); 497 } 498 int main(void) 499 { 500 for (int i = 2;i <= 1e6;++i) lg[i] = lg[i/2] + 1; 501 scan(n); 502 for (int i = 1;i <= n;++i) scan(a[i]),Sa[i] =-(1e9+1); 503 for (int i = 1;i <= n;++i) scan(b[i]),Sb[i] = (1e9+1); 504 ll ans = 0; 505 for (int i = n;i;--i) 506 { 507 updA(i,a[i]); 508 updB(i,b[i]); 509 if (mx(i) > mn(i)) continue; 510 int l = i-1,r = i; 511 for (int p = 1 << lg[n - i + 1];p;p >>= 1) 512 { 513 if (p + l <= n && mx(l+p) < mn(l+p)) l += p; 514 if (p + r <= n && mx(r+p) <= mn(r+p)) r += p; 515 } 516 ans += r - l; 517 } 518 fo << ans << '\n'; 519 return 0; 520 } 521 ``` 522 523 **Another C++ code** 524 525 ``` 526 #include <bits/stdc++.h> 527 using namespace std; 528 529 const int N = int(1e6) + 5; 530 int a[N], b[N], n; 531 int lfa[N], rga[N], lfb[N], rgb[N], nxt[N]; 532 533 void calc_max(int *a, int *lf, int *rg) { 534 stack <int> st; 535 a[n] = int(1e9) + 1; 536 537 for (int i = 0; i <= n; ++i) { 538 while (!st.empty() && a[st.top()] < a[i]) { 539 rg[st.top()] = i; 540 st.pop(); 541 } 542 543 lf[i] = st.empty() ? -1 : st.top(); 544 st.push(i); 545 } 546 } 547 548 int naive() { 549 int res = 0; 550 for (int i = 0; i < n; ++i) 551 for (int j = i; j < n; ++j) 552 if (*max_element(a + i, a + j + 1) == *min_element(b + i, b + j + 1)) 553 res++; 554 return res; 555 } 556 557 bool read() { 558 559 if (!(cin >> n)) 560 return false; 561 562 for (int i = 0; i < n; ++i) 563 assert(scanf("%d", &a[i]) == 1); 564 for (int i = 0; i < n; ++i) 565 assert(scanf("%d", &b[i]) == 1); 566 } 567 568 void solve() { 569 calc_max(a, lfa, rga); 570 571 for (int i = 0; i < n; ++i) 572 b[i] = -b[i]; 573 calc_max(b, lfb, rgb); 574 575 map <int, int> pos, last; 576 577 for (int i = 0; i < n; ++i) { 578 b[i] = -b[i]; 579 nxt[i] = n; 580 581 if (!pos.count(b[i])) 582 pos[b[i]] = i; 583 else 584 nxt[last[b[i]]] = i; 585 last[b[i]] = i; 586 } 587 588 long long res = 0; 589 590 for (int i = 0; i < n; ++i) { 591 if (!pos.count(a[i])) 592 continue; 593 594 int pb = pos[a[i]]; 595 596 while (nxt[pb] <= i) { 597 pb = nxt[pb]; 598 if (lfb[pb] != -1 && b[lfb[pb]] == b[pb]) 599 lfb[pb] = lfb[lfb[pb]]; 600 } 601 pos[a[i]] = pb; 602 603 for (int t = 0; t < 2 && pb < n; ++t, pb = nxt[pb]) { 604 int lf = max(lfa[i], lfb[pb]); 605 int rg = min(rga[i], rgb[pb]); 606 607 if (lf < min(i, pb) && max(i, pb) < rg) 608 res += (min(i, pb) - lf) * 1ll * (rg - max(i, pb)); 609 } 610 } 611 612 cout << res << endl; 613 } 614 615 int main() { 616 while (read()) 617 solve(); 618 return 0; 619 } 620 ``` 621 622  What if you need to count (*l*1, *r*1, *l*2, *r*2), 1 ≤ *l*1 ≤ *r*1 ≤ *n*, 1 ≤ *l*2 ≤ *r*2 ≤ *n* and . 623 624 Hint:[Take idea from this problem](//codeforces.com/contest/602/problem/D). 625 626 **C++ code for Bonus** 627 628 ``` 629 const int mod = 1e9 + 7; 630 int a[1 << 20]; 631 int b[1 << 20]; 632 int st[1 << 20]; 633 int dr[1 << 20]; 634 map < int , ll > A,B; 635 int main(void) 636 { 637 int n; 638 IOS; 639 fi>>n; 640 for (int i = 1;i <= n;++i) fi>>a[i]; 641 for (int i = 1;i <= n;++i) fi>>b[i]; 642 deque < int > d; 643 for (int i = 1;i <= n;++i) 644 { 645 while (!d.empty() && a[d.back()] < a[i]) d.pop_back(); 646 if (d.empty()) st[i] = 0; 647 else st[i] = d.back(); 648 d.push_back(i); 649 } 650 d.clear(); 651 for (int i = n;i;--i) 652 { 653 while (!d.empty() && a[d.back()] <= a[i]) d.pop_back(); 654 if (d.empty()) dr[i] = n+1; 655 else dr[i] = d.back(); 656 d.push_back(i); 657 } 658 for (int i = 1;i <= n;++i) 659 A[a[i]] += 1ll * (i - st[i]) * (dr[i] - i); 660 while (!d.empty()) d.pop_back(); 661 for (int i = 1;i <= n;++i) 662 { 663 while (!d.empty() && b[d.back()] > b[i]) d.pop_back(); 664 if (d.empty()) st[i] = 0; 665 else st[i] = d.back(); 666 d.push_back(i); 667 } 668 d.clear(); 669 for (int i = n;i;--i) 670 { 671 while (!d.empty() && b[d.back()] >= b[i]) d.pop_back(); 672 if (d.empty()) dr[i] = n+1; 673 else dr[i] = d.back(); 674 d.push_back(i); 675 } 676 for (int i = 1;i <= n;++i) 677 B[b[i]] += 1ll * (i - st[i]) * (dr[i] - i); 678 for (auto &it : A) it.y %= mod; 679 for (auto &it : B) it.y %= mod; 680 int ans = 0; 681 for (auto it : A) 682 ans = (ans + 1ll * it.y * B[it.x]) % mod; 683 fo << ans << '\n'; 684 return 0; 685 } 686 ``` 687 688 [E. Mike and Geometry Problem](//codeforces.com/contest/689/problem/E) 689 690 Author:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina") 691 692 Developed:[I_Love_Tina](/profile/I_Love_Tina "Candidate Master I_Love_Tina"),[ThatMathGuy](/profile/ThatMathGuy "Candidate Master ThatMathGuy") 693 694 Let define the following propriety:if the point *i* is intersected by *p* segments then in our sum it will be counted  times,so our task reduce to calculate how many points is intersected by *i* intervals 1 ≤ *i* ≤ *n*.Let *dp*[*i*] be the number of points intersected by *i* intervals.Then our answer will be . We can easily calculate array *dp* using a map and partial sum trick,[here you can find about it](//codeforces.com/contest/612/problem/D). 695 696 The complexity and memory is  and *O*(*n*). 697 698 **C++ code** 699 700 ``` 701 # include <bits/stdc++.h> 702 using namespace std; 703 # define fi cin 704 # define fo cout 705 # define x first 706 # define y second 707 const int nmax = 2e5 + 5; 708 const int mod = 1e9 + 7; 709 int pow(int a,int b,int mod) 710 { 711 int ans = 1; 712 while (b) 713 { 714 if (b&1) ans = (1ll * ans * a) % mod; 715 a = (1ll * a * a) % mod; 716 b /= 2; 717 } 718 return ans; 719 } 720 int f[nmax];//factorial 721 int c[nmax];//inverse of factorial 722 map < int , int > s; 723 int C(int n,int k) // combination 724 { 725 int ans = (1ll * f[n] * c[k]) % mod; 726 return (1ll * ans * c[n - k]) % mod; 727 } 728 main(void) 729 { 730 int n,k; 731 int ans = 0; 732 ios_base :: sync_with_stdio(0); 733 fi>>n>>k;assert(1 <= k && k <= n && n <= 2e5); 734 f[0] = c[0] = 1; 735 for (int i = 1;i <= n;++i) f[i] = (1ll * f[i-1] * i) % mod,c[i] = pow(f[i],mod-2,mod); 736 for (int i = 1;i <= n;++i) 737 { 738 int a,b; 739 fi>>a>>b; 740 assert(-1e9 <= a && a <= b && b <= 1e9); 741 ++s[a];--s[b+1]; 742 } 743 int l = s.begin()->x; 744 int sum = 0; 745 for (auto it : s) 746 { 747 int dist = it.x - l; 748 if (sum >= k) ans += (1ll * C(sum,k) * dist) % mod; 749 ans = (ans >= mod ? ans - mod : ans); 750 sum += it.y; 751 l = it.x; 752 } 753 return fo << ans << '\n',0; 754 } 755 ``` 756 757 **Another C++ solution** 758 759 ``` 760 #include <bits/stdc++.h> 761 762 #define ll long long 763 #define ld long double 764 765 using namespace std; 766 767 const int mod = 1e9+7; 768 769 ll pp(ll x, int y) 770 { 771 if (!y) return 1; 772 ll t = pp(x,y/2); 773 t = 1ll*t*t; 774 t%=mod; 775 if (y%2) t*=1ll*x; 776 t%=mod; 777 return t; 778 } 779 780 int n,k; 781 782 struct s 783 { 784 int x; 785 int y; 786 }; 787 788 s a[2*200000]; 789 790 ll c[200001]; 791 792 void gen() 793 { 794 ll b = 1; 795 796 c[k] = 1; 797 for (int i=k+1; i<=n; i++) 798 b*= i,b%=mod,b*=pp(i-k,mod-2),b%=mod,c[i]=b; 799 } 800 801 ll ans = 0; 802 803 int main() 804 { 805 ios_base::sync_with_stdio(false); 806 cin.tie(0); 807 808 cin>>n>>k; 809 810 gen(); 811 812 for (int i=0; i<n; i++) 813 cin>>a[2*i].x>>a[2*i+1].x,a[2*i].y = 1,a[2*i+1].y=-1,a[2*i+1].x++; 814 815 sort(a,a+2*n, [] (s x, s y) { if (x.x!=y.x) return (x.x<y.x); return (x.y>y.y);}); 816 817 int last = a[0].x; 818 int now = 0; 819 820 for (int i=0; i<2*n;) 821 { 822 int d = a[i].x; 823 ans += 1ll * c[now] * (d-last); 824 ans%=mod; 825 while (a[i].x==d) 826 now+=a[i].y,i++; 827 last = d; 828 } 829 830 cout<<ans; 831 832 return 0; 833 } 834 ``` 835 836  what if  where *l*, *r* are given in input. 837 838 I'm really sorry that problem *A* was harder than ussually.