fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int lli;
  4. typedef long double ld;
  5. /*
  6. #include <chrono> 
  7. using namespace std::chrono;
  8. #include <boost/multiprecision/cpp_lli.hpp> 
  9. using namespace boost::multiprecision;
  10. */
  11. /*
  12. #include <ext/pb_ds/assoc_container.hpp> 
  13. #include <ext/pb_ds/tree_policy.hpp> 
  14. using namespace __gnu_pbds; 
  15. #define ordered_set tree<lli, null_type,less_equal<lli>, rb_tree_tag,tree_order_statistics_node_update> 
  16. //remove _equal from less_equal to make it ordered set , currently it is ordered_multiset
  17. */
  18. #define pb push_back
  19. const lli mod=1e9+7;
  20. const lli mod1=998244353;
  21. #define fir first
  22. #define sec second
  23. #define plli pair<lli,lli>
  24. #define pplli pair<lli,plli>
  25. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
  26. lli power(lli a, lli b) {
  27.     lli res = 1;
  28.     while (b > 0) {
  29.         if (b & 1)
  30.             res = res * a;
  31.         a = a * a;
  32.         b >>= 1;
  33.     }
  34.     return res;
  35. }
  36. lli powermod(lli a, lli b) 
  37. {
  38.     lli res = 1;
  39.     while (b > 0) {
  40.         if (b & 1)
  41.             res = ((res%mod)*(a%mod))%mod;
  42.         a = (a * a)%mod;
  43.         b >>= 1;
  44.     }
  45.     return res%mod;
  46. }
  47. int main()
  48. {
  49.     fastio
  50.     lli T,i,j;
  51.     T=1;
  52.     cin>>T;
  53.     for(lli t=1;t<=T;t++)
  54.     {
  55.         lli n,c;
  56.         cin>>n>>c;
  57.         lli x,y;
  58.         map<lli,lli> mp;
  59.         for(i=0;i<n;i++)
  60.         {
  61.             cin>>x>>y;
  62.             mp[x+1]++,mp[y]--;
  63.         }
  64.         lli cur=0;
  65.         vector<plli> v;
  66.         lli prev=0;
  67.         for(plli p:mp)
  68.         {
  69.             v.pb({cur,p.fir-prev});
  70.             cur+=p.sec;
  71.             prev=p.fir;
  72.         }
  73.         sort(v.begin(),v.end(),greater<plli> ());
  74.         lli n1=v.size();
  75.         lli ans=0;
  76.         for(i=0;i<n1;i++)
  77.         {
  78.             if(c<v[i].sec)
  79.             {
  80.                 ans+=(c*v[i].fir);
  81.                 c=0;
  82.                 break;
  83.             }
  84.             else
  85.             {
  86.                 ans+=(v[i].fir*v[i].sec);
  87.                 c-=v[i].sec;
  88.             }
  89.         }
  90.         cout<<"Case #"<<t<<": "<<ans+n<<"\n";
  91.     }   
  92.     return 0;
  93. }
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
Time limit exceeded #stdin #stdout 5s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/suY1EE
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!