- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 47 lines of C++ from the credited upstream file 2102.cpp.
- The implementation visibly relies on sequence storage, work queue.
- No explicit loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1struct Location {2 string name;3 int score;4 Location(const string& name, int score)5 : name(std::move(name)), score(score) {}6};7 8class SORTracker {9 public:10 void add(const string& name, int score) {11 l.emplace(name, score);12 if (l.size() > k + 1) {13 const Location location = l.top();14 l.pop();15 r.emplace(location.name, location.score);16 }17 }18 19 string get() {20 const string name = l.top().name;21 if (!r.empty()) {22 const Location location = r.top();23 r.pop();24 l.emplace(location.name, location.score);25 }26 ++k;27 return name;28 }29 30 private:31 struct CompareLeftMinHeap {32 bool operator()(const Location& a, const Location& b) {33 return a.score == b.score ? a.name < b.name : a.score > b.score;34 }35 };36 37 struct CompareRightMaxHeap {38 bool operator()(const Location& a, const Location& b) {39 return a.score == b.score ? a.name > b.name : a.score < b.score;40 }41 };42 43 priority_queue<Location, vector<Location>, CompareLeftMinHeap> l;44 priority_queue<Location, vector<Location>, CompareRightMaxHeap> r;45 int k = 0;46};47