Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class tracker_inter
- {
- public:
- set<pair<int, int>> forbidden;
- int pt_add(int stuff)
- {
- pair<int, int> previn = {stuff, stuff};
- if(!forbidden.empty() && forbidden.upper_bound({stuff, 2e9})!=forbidden.begin())
- {
- previn = *prev(forbidden.upper_bound({stuff, 2e9}));
- }
- if(previn.second==stuff-1)
- {
- forbidden.erase(previn);
- previn.second++;
- }
- else
- {
- previn = {stuff, stuff};
- }
- forbidden.insert(previn);
- if(next(forbidden.find(previn))!=forbidden.end())
- {
- auto thing = *next(forbidden.find(previn));
- if(thing.first==previn.second+1)
- {
- forbidden.erase(thing); forbidden.erase(previn);
- previn.second = thing.second;
- forbidden.insert(previn);
- }
- }
- return 1;
- }
- };
- long long solve(vector<int> heights)
- {
- tracker_inter Rail;
- int n = heights.size();
- long long ans = 0;
- map<int, vector<int>> posi;
- for(int i=0; i<n; i++)
- {
- posi[heights[i]].push_back(i);
- }
- for(auto lin : posi)
- {
- for(auto stuff : lin.second)
- {
- Rail.pt_add(stuff);
- }
- for(auto stuff : lin.second)
- {
- auto thing = *prev(Rail.forbidden.upper_bound(make_pair(stuff, 2e5)));
- ans += thing.second - thing.first + 1;
- }
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment