fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define NAME "slime"
  3. #define ll long long
  4. #define N int(1e6)
  5. using namespace std;
  6. ll n,k,ans;
  7. ll x;
  8. unordered_map<ll,ll>cnt;
  9. void sub1()
  10. {
  11.     ll min1=1e18,max1=-1e18;
  12.  
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         ll a,b,c,t;
  16.         cin>>a>>b>>c>>t;
  17.         min1=min(min1,t);
  18.         ll cur=0;
  19.         while(cur<c)
  20.         {
  21.             t++;
  22.             cur+=a;
  23.             if(cur>=x) cnt[t]++;
  24.         }
  25.         while(cur>=x)
  26.         {
  27.             t++;
  28.             cur-=b;
  29.             if(cur>=x) cnt[t]++;
  30.         }
  31.         max1=max(max1,t);
  32.     }
  33.     for(int i=min1;i<=max1;i++) //cout<<i<<" "<<cnt[i]<<'\n';
  34.     {
  35.         if(cnt[i]>=k) ans++;
  36.     }
  37.     cout<<ans;
  38. }
  39. ll pre[N+10];
  40. void sub2()
  41. {
  42.     ll sl=0;
  43.     set<ll>st;
  44.     vector<ll>v;
  45.     for(int i=1;i<=n;i++)
  46.     {
  47.         ll a,b,c,t;
  48.         cin>>a>>b>>c>>t;
  49.  
  50.         ll l=x/a+t;
  51.         if(((l-t)*a)<x) l++;
  52.         ll r=c/a+t;
  53.         if(((r-t)*a)<c) r++;
  54.         if(l>r) continue;
  55.         cnt[l]++;
  56.         cnt[r+1]--;
  57.         //cout<<i<<" "<<l<<" "<<r<<'\n';
  58.         st.insert(l);
  59.         st.insert(r+1);
  60.         sl++;
  61.         ll cur=(r-t)*a;
  62.         if(cur-b<x) continue;
  63.         ll cur1=cur;
  64.         cur-=x;
  65.         ll r1=((cur/b)+r);
  66.         if((cur1-(r1-r)*b)<x) r1--;
  67.         if(r>r1)  continue;
  68.         cnt[r+1]++;
  69.         cnt[r1+1]--;
  70.         st.insert(r+1);
  71.         st.insert(r1+1);
  72.         sl++;
  73.         //cout<<i<<" "<<r+1<<" "<<r1<<'\n';
  74.     }
  75.     if(sl==0)
  76.     {
  77.         cout<<0;
  78.         return;
  79.     }
  80.     for(auto x:st) v.push_back(x);
  81.     for(int i=0;i<v.size()-1;i++) //cout<<x<<" "<<cnt[x]<<'\n';
  82.     {
  83.         ll x=v[i];
  84.         ll y=v[i+1]-1;
  85.         pre[i]=pre[i-1]+cnt[x];
  86.         //cout<<x<<" "<<pre[i]<<'\n';
  87.         if(pre[i]>=k) ans+=(y-x)+1;
  88.     }
  89.     cout<<ans;
  90. }
  91. int main()
  92. {
  93.     ios::sync_with_stdio(0);
  94.     cin.tie(0);
  95.     cout.tie(0);
  96.     if(fopen(NAME ".inp", "r"))
  97.     {
  98.         freopen(NAME ".inp", "r", stdin);
  99.         freopen(NAME ".out", "w", stdout);
  100.     }
  101.  
  102.     cin>>n>>k>>x;
  103.     if(n<=1000 && k<=1000)
  104.     {
  105.         sub1();
  106.         return 0;
  107.     }
  108.     sub2();
  109.  
  110.  
  111.     return 0;
  112. }
  113.  
  114.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HUP2L3
language:
C++ (gcc 8.3)
created:
6 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!