SHARE
TWEET

12321 - Gas Stations

a guest Sep 21st, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //12321 - Gas Stations
  2. //Karikó Csongor
  3. #include <iostream>
  4. #include <algorithm>
  5. #define MAX_G 10010
  6. using namespace std;
  7.  
  8. int L, G, a, b;
  9. struct range{
  10.     int x, y;
  11.  
  12.     range(int _x, int _y) { x = _x;
  13.         y = _y;
  14.     }
  15.  
  16.     range(){}
  17. };
  18.  
  19. bool cmp (const range& left, const range& right){
  20.     if (left.x == right.x) return left.y > right.y;
  21.     return left.x < right.x;
  22. }
  23.  
  24. range ranges[MAX_G];
  25.  
  26. int main(){
  27.     cin >> L >> G;
  28.     do{
  29.         for (int i = 0; i < G; ++i){
  30.             cin >> a >> b;
  31.             ranges[i].x = a - b;
  32.             ranges[i].y = a + b;
  33.         }
  34.  
  35.         sort(ranges, ranges + G, cmp);
  36.  
  37.         int maxLen = 0;
  38.         int newMaxLen = 0;
  39.         int deleted = 0;
  40.         for (int i = 0; i < G; ++i) {
  41.             while(ranges[i].x <= maxLen && i < G){
  42.                 //cout << "try " << ranges[i].x << " - " << ranges[i].y << '\n';
  43.                 newMaxLen = max(newMaxLen, ranges[i].y);
  44.                 ++i;
  45.             }
  46.  
  47.             deleted++;
  48.  
  49.             if (newMaxLen >= L) break;
  50.  
  51.             if (newMaxLen == maxLen && maxLen < L) {
  52.                 // no solution
  53.                 //cout << "maxLen: " << maxLen << '\n';
  54.                 deleted = -1;
  55.                 break;
  56.             } else
  57.                 --i;
  58.  
  59.             //cout << "found\n";
  60.  
  61.             maxLen = newMaxLen;
  62.            
  63.         }
  64.  
  65.         if (deleted == -1 || newMaxLen < L) cout << "-1\n";
  66.         else
  67.         cout << G - deleted << '\n';
  68.  
  69.         cin >> L >> G;
  70.     } while (L > 0);
  71.  
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top