Untitled

/*

1. logn
2. logn
3. k+logn

*/

#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
using namespace std;

struct Record {
	int customerID;
	int revenue;
	Record(): customerID(-1), revenue(0) {} // !!!!!!!!!!!! need this default constructor
	Record(int customerID, int revenue): customerID(customerID), revenue(revenue) { }
	bool operator<(const Record &that) const {
		return revenue < that.revenue;
	}
};


class CustomerRevenue {
public:
	void insert(int revenue){
		Record r = Record(customerCounter, revenue);
		// mySet.emplace(customerCounter, revenue);
		mySet.emplace(r);
		m[customerCounter] = r;
		customerCounter += 1;
	}

	void insert(int revenue, int referID){
		Record r = Record(customerCounter, revenue);
		mySet.emplace(r);
		m[customerCounter] = r;
		customerCounter += 1;

		Record referred = m[referID];
		// referred.revenue += revenue;
		int tmpRevenue = referred.revenue + revenue;
		mySet.erase(referred);
		Record newRecord = Record(referID, tmpRevenue);
		m[referID] = newRecord;
		mySet.emplace(newRecord);
	}

	vector<int> getKLowestRevenue(int k, int targetRevenue){
		vector<int> v;
		Record helper = Record(-1, targetRevenue); // !!!
		auto it = mySet.upper_bound(helper); // !!!
		for(int i = 0; i < k; i++){
			int val = it->revenue;
			v.push_back(val);
			++it;
		}

		return v;
	}

private:
	set<Record> mySet;
	unordered_map<int, Record> m; // customerID, Record // 
	int customerCounter = 0;

};

int main(){
	CustomerRevenue system;
	system.insert(20);
	cout << "insert(20) finishes" << endl;
	system.insert(40, 0);
	cout << "insert(40, 0) finishes" << endl;
	vector<int> tmp = system.getKLowestRevenue(1, 50);

	for(int i = 0; i < tmp.size(); i++){ // print 60
		cout << tmp[i] << " ";
	}


	CustomerRevenue system2;
	system2.insert(20);
	system2.insert(500);
	system2.insert(30, 0);
	system2.insert(50, 0);
	system2.insert(20, 0);
	vector<int> tmp2 = system2.getKLowestRevenue(2, 100);
	for(int i = 0; i < tmp2.size(); i++){ // print 120 500
		cout << tmp2[i] << " ";
	}


	return 0;

}