fork download 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <unordered_set>
  5. using namespace std;
  6. struct Node{
  7. 	int x;
  8. 	int s;
  9. 	int e;
  10. 	int m;
  11. 	Node* l;
  12. 	Node* r;
  13. 	Node(int X, int S, int E, int M, Node* L = NULL, Node* R = NULL): x(X), s(S), e(E), m(M), l(L), r(R) {}
  14. };
  15. struct Booking{
  16. 	int s;
  17. 	int e;
  18. 	int car;
  19. 	Booking(int i, int S, int E): car(i), s(S), e(E) {}
  20. };
  21. class Register{
  22. private:
  23. 	Node *head;
  24. 	multimap<int,int> starts;
  25. 	multimap<int,int> ends;
  26. 	vector<Booking> v;
  27. 	void intersect(Node *node, int x, unordered_set<int> &cars){
  28. 		if(!node)	return;
  29. 		if(node->m<=x)	return intersect(node->r,x,cars);
  30. 		if(node->s>x)	return intersect(node->l,x,cars);
  31. 		if(node->e>x)	cars.insert(v[node->x].car);
  32. 		intersect(node->l,x,cars);
  33. 		intersect(node->r,x,cars);
  34. 	}
  35. 	Node* insert(Node* &head, Node* node){
  36. 		if(!head)	return head = node;
  37. 		if(head->s<=node->s)	return insert(head->r,node);
  38. 		head->m = max(head->m, node->m);
  39. 		return insert(head->l,node);
  40. 	}
  41. public:
  42. 	unordered_set<int> getBookedCars(int s, int e){
  43. 		unordered_set<int> cars;
  44. 		for(auto it = starts.lower_bound(s); it!=starts.end()&&it->first<e; it++)
  45. 			cars.insert(v[it->second].car);
  46. 		for(auto it = ends.upper_bound(s); it!=ends.end()&&it->first<=e; it++)
  47. 			cars.insert(v[it->second].car);
  48. 		intersect(head,s,cars);
  49. 		return cars;
  50. 	}
  51. 	void addBooking(int car, int s, int e){
  52. 		int i = v.size();
  53. 		v.push_back(Booking(car,s,e));
  54. 		starts.insert({s,i});
  55. 		ends.insert({e,i});
  56. 		Node* node = new Node(i,s,e,e);
  57. 		insert(head, node);
  58. 	}
  59. };
  60. int main() {
  61. 	// your code goes here
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yUB1Pq
booking cars for a period, interval tree
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!