mickypinata

USACO-T005: Milking Cows

Sep 20th, 2021
549
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: milk2
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. struct event {
  11.     int t, add;
  12.     event(int t, int add): t(t), add(add) {};
  13.     bool operator < (const event &rhs){
  14.         if(t != rhs.t){
  15.             return t < rhs.t;
  16.         }
  17.         return add < rhs.add;
  18.     }
  19. };
  20.  
  21. vector<event> events;
  22.  
  23. int main(){
  24.  
  25.     freopen("milk2.in", "r", stdin);
  26.     freopen("milk2.out", "w", stdout);
  27.  
  28.     int n;
  29.     scanf("%d", &n);
  30.     for(int i = 1; i <= n; ++i){
  31.         int st, ed;
  32.         scanf("%d%d", &st, &ed);
  33.         events.emplace_back(st, 1);
  34.         events.emplace_back(ed, 2);
  35.     }
  36.     sort(events.begin(), events.end());
  37.  
  38.     int mxMilk = 0;
  39.     int mxIdle = 0;
  40.     int stMilk = -1;
  41.  
  42.     int last = events.front().t;
  43.     int cnt = 0;
  44.     for(event e : events){
  45.         int t = e.t;
  46.         int add = e.add;
  47.         if(t != last){
  48.             if(cnt != 0){
  49.                 if(stMilk == -1){
  50.                     stMilk = last;
  51.                 }
  52.                 mxMilk = max(mxMilk, t - stMilk);
  53.             } else {
  54.                 stMilk = -1;
  55.                 mxIdle = max(mxIdle, t - last);
  56.             }
  57.             last = t;
  58.         }
  59.         if(add == 1){
  60.             ++cnt;
  61.         } else if(add == 2){
  62.             --cnt;
  63.         }
  64.     }
  65.     cout << mxMilk << ' ' << mxIdle << '\n';
  66.  
  67.     fclose(stdin);
  68.     fclose(stdout);
  69.  
  70.     return 0;
  71. }
  72.  
RAW Paste Data