The5threic1-1

Tracking_interval

Apr 21st, 2024
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | Source Code | 0 0
  1. class tracker_inter
  2. {
  3.     public:
  4.         set<pair<int, int>> forbidden;
  5.        
  6.         int clear()
  7.         {
  8.             forbidden.clear();
  9.             return 0;
  10.         }
  11.    
  12.             bool inter_check(int st, int endi)
  13.         {
  14.             auto itr = forbidden.upper_bound({st, st});
  15.             if(itr==forbidden.end() || itr->first>endi)
  16.             {
  17.                 if(itr==forbidden.begin() || prev(itr)->second<st)
  18.                 {
  19.                     return 0;
  20.                 }
  21.             }
  22.             return 1;
  23.         }
  24.  
  25.         int pt_remove(int stuff)
  26.         {
  27.             if(!this->inter_check(stuff, stuff))
  28.             {
  29.                 return 0;
  30.             }
  31.             pair<int, int> previ = *prev(forbidden.upper_bound({stuff, 1e9}));
  32.             forbidden.erase(previ);
  33.            
  34.             if(previ.first<=stuff && previ.second>=stuff)
  35.             {
  36.                 pair<int, int> insi1 = {previ.first, stuff-1}, insi2 = {stuff+1, previ.second};
  37.                 if(insi1.first<=insi1.second)
  38.                 {
  39.                     forbidden.insert(insi1);
  40.                 }  
  41.                 if(insi2.first<=insi2.second)
  42.                 {
  43.                     forbidden.insert(insi2);
  44.                 }
  45.             }
  46.             return 1;  
  47.         }
  48.        
  49.         int pt_add(int stuff)
  50.         {
  51.             if(this->inter_check(stuff, stuff))
  52.             {
  53.                 return 0;
  54.             }
  55.             pair<int, int> previn = {stuff, stuff};
  56.             if(!forbidden.empty() && forbidden.upper_bound({stuff, 2e9})!=forbidden.begin())
  57.             {
  58.                 previn = *prev(forbidden.upper_bound({stuff, 2e9}));
  59.             }
  60.             if(previn.second==stuff-1)
  61.             {
  62.                 forbidden.erase(previn);
  63.                 previn.second++;   
  64.             }
  65.             else
  66.             {
  67.                 previn = {stuff, stuff};
  68.             }  
  69.             forbidden.insert(previn);  
  70.             if(next(forbidden.find(previn))!=forbidden.end())
  71.             {
  72.                 auto thing = *next(forbidden.find(previn));
  73.                 if(thing.first==previn.second+1)
  74.                 {
  75.                     forbidden.erase(thing); forbidden.erase(previn);
  76.                     previn.second = thing.second;
  77.                     forbidden.insert(previn);
  78.                 }
  79.             }
  80.             return 1;      
  81.         }  
  82. };
Advertisement
Add Comment
Please, Sign In to add comment