fork download
  1. #include<bits/stdc++.h>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  6. #define MAX 500050
  7.  
  8. #define ll long long
  9. #define ld long double
  10. #define lli long long int
  11.  
  12. #define pb push_back
  13. #define INF 100000000000000
  14. #define mod 1000000007
  15.  
  16. // trignometric function always give value in Radians only
  17. #define PI acos(-1) //3.1415926535897932384626433832795028
  18. #define dsin(degree) sin(degree*(PI/180.0))
  19. #define dcos(degree) cos(degree*(PI/180.0))
  20. #define dtan(degree) tan(degree*(PI/180.0))
  21.  
  22. #define rsin(radian) sin(radian)
  23. #define rcos(radian) cos(radian)
  24. #define rtan(radian) tan(radian)
  25.  
  26. #define counttrailingzeroes(n) __builtin_ctzll(n)
  27. #define countsetbits(n) __builtin_popcountll(n)
  28.  
  29. #define mem0(a) memset(a,0,sizeof(a))
  30. #define mem1(a) memset(a,-1,sizeof(a))
  31. #define memf(a) memset(a,false,sizeof(a))
  32.  
  33. #define loop(i,n) for (lli i = 0; i < n; i++)
  34. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  35.  
  36. #define all(v) v.begin(),v.end()
  37. #define rall(v) v.rbegin(),v.rend()
  38. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  39. #define sz(x) int(x.size())
  40. #define F first
  41. #define S second
  42.  
  43. #define mii map<lli,lli>
  44.  
  45. #define pii pair<lli,lli>
  46.  
  47. #define vi vector<lli>
  48. #define vvi vector<vi>
  49. #define vpi vector<pii>
  50. #define vbool vector<bool>
  51.  
  52. #define seti set<lli>
  53.  
  54. #define gcd(a,b) __gcd((a),(b))
  55. #define lcm(a,b) (a/gcd(a,b))*b
  56. #define abs(x) ((x < 0)?-(x):x)
  57. #define isvowel(v) (0x208222>>(v&0x1f))&1
  58.  
  59. #define endl '\n'
  60.  
  61. template <typename Head>
  62. void print(Head&& head)
  63. {
  64. cout<<head<<endl;
  65. }
  66. template <typename Head, typename... Tail>
  67. void print(Head&& head, Tail... tail)
  68. {
  69. cout<<head<<" ";
  70. print(tail...);
  71. }
  72.  
  73. #define scanarr(a,n) for(lli i=0;i<n;i++) cin>>a[i];
  74. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  75.  
  76. #define printarr(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
  77. #define printvec(vec) for(auto xt : vec) cout<<xt<<" "; cout<<"\n";
  78.  
  79. #define FD(N) fixed<<setprecision(N)
  80.  
  81. #define deb(x) cout<<#x<<" "<<x<<endl;
  82.  
  83. /*
  84. 1D vector - vi dp(n,value);
  85. */
  86.  
  87. lli mceil(lli a,lli b){ return(a/b + (a%b != 0)); }
  88.  
  89. lli mfloor(lli a,lli b){ return(a/b); }
  90.  
  91. ll modmul(ll a, ll b,ll MOD = mod) {
  92. return ((a%MOD) * (b%MOD)) % MOD;
  93. }
  94.  
  95. ll modadd(ll a, ll b,ll MOD = mod){
  96. return((a%MOD)+(b%MOD)+MOD)%MOD;
  97. }
  98.  
  99. ll modsub(ll a, ll b,ll MOD = mod){
  100. return((a%MOD) - (b%MOD) + MOD)%MOD;
  101. }
  102.  
  103. lli fastexpo(lli a,lli b ,lli MOD = mod){
  104. a = a%MOD;
  105. lli ans=1;
  106. while(b){
  107. if(b&1)
  108. ans=(ans*1ll*a)%MOD;
  109. a=(a*1ll*a)%MOD;
  110. b=b/2;
  111. }
  112. return ans;
  113. }
  114.  
  115.  
  116. vector<int>all_div[200001];
  117. void alldivisors(){
  118. for(int i=1;i<=200000;++i){
  119. for(int j=i;j<=200000;j+=i)
  120. all_div[j].pb(i);
  121. }
  122. }
  123.  
  124.  
  125. bool ispower2(lli n){
  126. return(n and (n&(n-1))==0 );
  127. }
  128. pii findIntersection(vpi vc, lli n)
  129. {
  130. lli l = -1;
  131. lli r = INF;;
  132. loop(i,sz(vc))
  133. {
  134. l = max(l,vc[i].F);
  135. r = min(r,vc[i].S);
  136. }
  137. return {l,r};
  138. }
  139.  
  140.  
  141. int main(){
  142. fastio
  143. lli tt =10000;
  144. cin>>tt;
  145. loop(ii,tt)
  146. {
  147. cout<<"Case #"<<ii+1<<": ";
  148. lli n,k;
  149. cin>>n>>k;
  150. vpi vc,vcc;
  151. lli pre[100005]={0};
  152. mii mp;
  153. lli maxi = -1;
  154. loop(i,n)
  155. {
  156. lli x,y;
  157. cin>>x>>y;
  158. vc.pb({x,y});
  159. maxi =max(maxi , x);
  160. maxi = max(maxi,y);
  161. }
  162. FOR(i,1,maxi+1)
  163. {
  164. lli cnt=0;
  165. loop(j,n)
  166. {
  167. if(i>vc[j].F and i<vc[j].S)
  168. cnt++;
  169. }
  170. if(cnt)
  171. vcc.pb({cnt,i});
  172. }
  173. sort(all(vcc));
  174. reverse(all(vcc));
  175. lli mini = min(k*1LL , sz(vcc)*1LL);
  176. lli tans = 0;
  177. loop(i,mini)
  178. tans += vcc[i].F;
  179. print(tans+n);
  180. }
  181. return 0;
  182. }
  183.  
  184.  
  185.  
Success #stdin #stdout 0.01s 8136KB
stdin
1
3 3
1 3
2 4
1 4
stdout
Case #1: 7