fork(2) download 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10.     int key;
  11. 	int prior;
  12. 	int cnt;
  13. 	node * l, * r;
  14. 	node(){}
  15. 	node (int _key) : key(_key), prior(rand()), cnt(1), l(0), r(0){}
  16. };
  17.  
  18. int cnt(node * v)
  19. {
  20. 	return v ? v->cnt : 0;
  21. }
  22.  
  23. void upd(node * v)
  24. {
  25. 	if (v) v->cnt = 1 + cnt(v->l) + cnt (v->r);
  26. }
  27.  
  28. void split (node * v, int key, node * & l, node * & r) {
  29. 	if (!v) l = r = 0;
  30. 	else if (key < v->key)
  31. 		split (v->l, key, l, v->l),  r = v;
  32. 	else
  33. 		split (v->r, key, v->r, r),  l = v;
  34.     upd(v);
  35. }
  36.  
  37. void insert (node * & v, node * add) {
  38. 	if (!v) v = add;
  39. 	else if (add->prior > v->prior)
  40. 		split (v, add->key, add->l, add->r),  v = add;
  41. 	else
  42. 		insert (add->key < v->key ? v->l : v->r, add);
  43.     upd(v);
  44. }
  45.  
  46. int get(node * v, int val)
  47. {
  48.     if (!v) return 0;
  49.     if (val == v->key) return 1 + cnt(v->r);
  50.     if (val < v->key)
  51.         return cnt(v->r) + 1 + get(v->l, val);
  52.     else
  53.         return get(v->r, val);
  54. }
  55.  
  56. node ** BIT;
  57. int s;
  58.  
  59. int get(int r, int val)
  60. {
  61.     int res = 0;
  62.     for(; r >= 0; r = (r & (r + 1)) - 1)
  63.         res += get(BIT[r], val);
  64.     return res;
  65. }
  66.  
  67. void add(int pos, int val)
  68. {
  69.     for(; pos < s; pos |= pos + 1)
  70.     {
  71.         node * add = new node(val);
  72.         insert(BIT[pos], add);
  73.     }
  74. }
  75.  
  76. int main()
  77. {
  78.     int n;
  79.     scanf("%d", &n);
  80.     getchar();
  81.     int l[n], r[n], type[n];
  82.     char c;
  83.     for(int i = 0; i < n; ++i)
  84.     {
  85.         c = getchar();
  86.         scanf("%d %d", l + i, r + i);
  87.         getchar();
  88.         type[i] = (c == '+') ? 0 : 1;
  89.     }
  90.     int z[n];
  91.     memcpy(z, l, sizeof(l));
  92.     sort(z, z + n);
  93.     s = unique(z, z + n) - z;
  94.     BIT = new node* [s];
  95.     for(int i = 0; i < n; ++i)
  96.     {
  97.         l[i] = lower_bound(z, z + s, l[i]) - z;
  98.         if (type[i])
  99.             printf("%d\n", get(l[i], r[i]));
  100.         else
  101.             add(l[i], r[i]);
  102.     }
  103.     return 0;
  104. }
  105.  
  106.  
Runtime error #stdin #stdout 0s 2900KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/oU6CrJ
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!