fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  4. uniform_real_distribution<> pp(0.0,1.0);
  5. #define int long long
  6. #define ld long double
  7. #define pii pair<int,int>
  8. #define piii pair<pii,int>
  9. #define mpp make_pair
  10. #define fi first
  11. #define se second
  12. const int inf=1e18;
  13. const int mod=998244353;
  14. const int maxn=100005;
  15. const int bl=650;
  16. const int maxs=655;
  17. const int maxm=200005;
  18. const int maxq=1000005;
  19. const int maxl=20;
  20. const int maxa=1000000;
  21. const int root=3;
  22. int power(int a,int n){
  23.     int res=1;
  24.     while(n){
  25.         if(n&1) res=res*a%mod;
  26.         a=a*a%mod;n>>=1;
  27.     }
  28.     return res;
  29. }
  30. const int iroot=power(3,mod-2);
  31. const int base=101;
  32.  
  33. int n,m,k[maxn],s[maxn],t[maxn];
  34. int cur[maxn];
  35. vector<pii> p;
  36.  
  37. bool check(int x){
  38.     for(int i=1;i<=m;i++) cur[i]=k[i];
  39.     priority_queue<pii,vector<pii>,greater<pii>> pq;
  40.     int pre=0;
  41.     for(pii d:p){
  42.         int cnt=inf;
  43.         if((d.fi-pre)<inf/x) cnt=(d.fi-pre)*x;
  44.         while(cnt && !pq.empty()){
  45.             int id=pq.top().se;
  46.             int num=min(cur[id],cnt);
  47.             cnt-=num;cur[id]-=num;
  48.             if(cur[id]==0) pq.pop();
  49.         }
  50.         pre=d.fi;
  51.         if(d.se<0 && cur[-d.se]!=0) return false;
  52.         else if(d.se>0) pq.push({t[d.se],d.se});
  53.     }
  54.     return true;
  55. }
  56.  
  57. void solve(){
  58.     cin >> m >> n;
  59.     for(int i=1;i<=m;i++){
  60.         cin >> k[i] >> s[i] >> t[i];
  61.         p.push_back({s[i],i});
  62.         p.push_back({t[i]+1,-i});
  63.     }
  64.     sort(p.begin(),p.end());
  65.     int l=1,r=inf,res=inf;
  66.     while(r>=l){
  67.         int mid=(l+r)>>1;
  68.         if(check(mid)) res=mid,r=mid-1;
  69.         else l=mid+1;
  70.     }
  71.     cout << res << '\n';
  72. }
  73.  
  74. signed main(){
  75.     freopen("schedule.inp","r",stdin);
  76.     freopen("schedule.out","w",stdout);
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL);cout.tie(NULL);
  79.     int test=1;//cin >> test;
  80.     while(test--) solve();
  81. }
  82.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5ZOGqo
language:
C++14 (gcc 8.3)
created:
2 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!