fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define task "slime"
  3. #define endl '\n'
  4. #define ii pair<int, int>
  5. #define iii pair<int, ii>
  6. #define fi first
  7. #define se second
  8. #define MASK(i) (1LL << (i))
  9. #define c_bit(i) __builtin_popcountll(i)
  10. #define BIT(x, i) ((x) & MASK(i))
  11. #define SET_ON(x, i) ((x) | MASK(i))
  12. #define SET_OFF(x, i) ((x) &~ MASK(i))
  13. #define ll long long
  14. #define pll pair <ll, ll>
  15. #define MingAnh signed main
  16. using namespace std;
  17.  
  18. const int MOD = 1e9+7;
  19. const int oo = 1e9;
  20. const int BASE = 311;
  21. const int N = 5e5;
  22. int n, k, x;
  23. int a[N + 20], b[N + 20], c[N + 20], t[N + 20];
  24. pll calc (int i){
  25.     ll l, r, up;
  26.     up = (c[i] + a[i] - 1) / a[i];
  27.     if (a[i] * up < x) return {0, 0};
  28.     l = t[i] + (x + a[i] - 1) / a[i];
  29.     r = t[i] + up + (a[i] * up - x + b[i] - 1) / b[i];
  30.     return {l, r};
  31. }
  32. namespace sub1{
  33.     int maxi = 0;
  34.     bool check(){
  35.         for (int i = 1; i <= n; ++i) maxi = max(maxi, t[i]);
  36.         return n <= 1000 && k <= 1000 & maxi <= 100000;
  37.     }
  38.  
  39.     int p[320000], ans = 0;
  40.  
  41.     void solve(){
  42.         for (int i = 1; i <= n; ++i){
  43.             ii res = calc(i);
  44.             p[res.fi]++;
  45.             p[res.se + 1]--;
  46.         }
  47.  
  48.         int cnt = 0;
  49.         for (int i = 1; i <= 300020; ++i){
  50.             cnt += p[i];
  51.             if (cnt >= k) ++ans;
  52.         }
  53.  
  54.         cout << ans;
  55.     }
  56. }
  57. namespace subfull{
  58.  
  59.     ll ans = 0;
  60.     vector <pll> event;
  61.  
  62.     void solve(){
  63.         for (int i = 1; i <= n; ++i){
  64.             ii res = calc(i);
  65.             event.push_back({res.fi, 1});
  66.             event.push_back({res.se + 1, -1});
  67.         }
  68.  
  69.         sort(event.begin(), event.end());
  70.  
  71.         int cnt = 0;
  72.         for (int i = 0; i < event.size(); ++i){
  73.             int j = i - 1;
  74.             while (j + 1 < event.size() && event[j + 1].fi == event[i].fi) cnt += event[++j].se;
  75.             if (cnt >= k && j + 1 < event.size()) ans += event[j + 1].fi - event[i].fi;
  76.         }
  77.  
  78.         cout << ans;
  79.     }
  80. }
  81. MingAnh()
  82. {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);cout.tie(0);
  85.     freopen(task".inp", "r", stdin);
  86.     freopen(task".out", "w", stdout);
  87.     cin >> n >> k >> x;
  88.     for (int i = 1; i <= n; ++i){
  89.         cin >> a[i] >> b[i] >> c[i] >> t[i];
  90.     }
  91.  
  92. //    if (sub1::check()) return sub1::solve(), 0;
  93.     subfull::solve();
  94.     return 0;
  95. }
  96. /*
  97. Making My Way aMing
  98.  
  99. */
  100.  
  101.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WqwsOy
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

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!