1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

class TopVotedCandidate {
public:
    TopVotedCandidate(std::vector<int>& persons, std::vector<int>& times) {
        int n = persons.size();
        tops.resize(n);
        times_ = times;
        std::unordered_map<int, int> votes;
        
        int top = -1;
        for (int i = 0; i < n; ++i) {
            ++votes[persons[i]];
            if (votes[persons[i]] >= votes[top]) {
                top = persons[i];
            }
            tops[i] = top;
        }
    }
    
    int q(int t) {
        auto it = std::lower_bound(times_.begin(), times_.end(), t + 1);
        if (it == times_.begin()) {
            return tops[0];
        }
        return tops[it - times_.begin() - 1];
    }
    
private:
    std::vector<int> tops;
    std::vector<int> times_;
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */