The5threic1-1

Calci region

Apr 21st, 2024
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | Source Code | 0 0
  1. class tracker_inter
  2. {
  3.     public:
  4.         set<pair<int, int>> forbidden;
  5.         int pt_add(int stuff)
  6.         {
  7.             pair<int, int> previn = {stuff, stuff};
  8.             if(!forbidden.empty() && forbidden.upper_bound({stuff, 2e9})!=forbidden.begin())
  9.             {
  10.                 previn = *prev(forbidden.upper_bound({stuff, 2e9}));
  11.             }
  12.             if(previn.second==stuff-1)
  13.             {
  14.                 forbidden.erase(previn);
  15.                 previn.second++;   
  16.             }
  17.             else
  18.             {
  19.                 previn = {stuff, stuff};
  20.             }  
  21.             forbidden.insert(previn);  
  22.             if(next(forbidden.find(previn))!=forbidden.end())
  23.             {
  24.                 auto thing = *next(forbidden.find(previn));
  25.                 if(thing.first==previn.second+1)
  26.                 {
  27.                     forbidden.erase(thing); forbidden.erase(previn);
  28.                     previn.second = thing.second;
  29.                     forbidden.insert(previn);
  30.                 }
  31.             }
  32.             return 1;      
  33.         }  
  34. };
  35. long long solve(vector<int> heights)
  36. {
  37.     tracker_inter Rail;
  38.     int n = heights.size();
  39.     long long ans = 0;
  40.     map<int, vector<int>> posi;
  41.     for(int i=0; i<n; i++)
  42.     {
  43.         posi[heights[i]].push_back(i); 
  44.     }
  45.     for(auto lin : posi)
  46.     {
  47.         for(auto stuff : lin.second)
  48.         {
  49.             Rail.pt_add(stuff);
  50.         }
  51.         for(auto stuff : lin.second)
  52.         {
  53.             auto thing = *prev(Rail.forbidden.upper_bound(make_pair(stuff, 2e5)));
  54.             ans += thing.second - thing.first + 1;     
  55.         }
  56.     }
  57.     return ans;
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment