codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/b332d3f430cc2f5d2e5e0fd92a9bce886b47d01f.png) 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 ![](https://espresso.codeforces.com/823d5850819cf15ecbb7b6a9bd0cdd7e7bcefea5.png) , so for each *k* we can count how many *a* satisfy the conditions 0 < *a* < *ak* < *ak*2 < *ak*3 ≤ *n*, their number is ![](https://espresso.codeforces.com/496118f94d91f79ba1cd215308ae2345458acbd6.png). Considering this, the final answer is ![](https://espresso.codeforces.com/2226afc1f7deada3299a47b529493e7264ca4091.png).
    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 ~ ![](https://espresso.codeforces.com/a739a9f39f0898eab24fd0ced777162393347da0.png), 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 ![](https://espresso.codeforces.com/aebe55e5e4612defb97db2fea41b42d82acea6a6.png). 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 ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) time and ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) 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 ![](https://espresso.codeforces.com/b332d3f430cc2f5d2e5e0fd92a9bce886b47d01f.png) 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 ![](https://espresso.codeforces.com/793bcb2619bef5a35a292ea339bdf729a2f7deed.png).
    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 ![](https://espresso.codeforces.com/5de4992493e20964ef4db5612fb8fa8a8f4e8e00.png) 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 ![](https://espresso.codeforces.com/91f153c1d45f331ffaa7f64b4bd68f5e18783b93.png). 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 ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) 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 ![](https://espresso.codeforces.com/b332d3f430cc2f5d2e5e0fd92a9bce886b47d01f.png) what if ![](https://espresso.codeforces.com/83f0dd7778dc896d348a7033ceaf6191ee732ef7.png) where *l*, *r* are given in input.
    837 
    838 I'm really sorry that problem *A* was harder than ussually.