fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define clr(x) memset((x), 0, sizeof(x))
  3. #define all(x) (x).begin(), (x).end()
  4. #define pb push_back
  5. #define mp make_pair
  6. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  7. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  8. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  9. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  10. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  11. #define in(x) int (x); input((x));
  12. #define x first
  13. #define y second
  14. #define less(a,b) ((a) < (b) - EPS)
  15. #define more(a,b) ((a) > (b) + EPS)
  16. #define eq(a,b) (fabs((a) - (b)) < EPS)
  17. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  18. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23.  
  24. struct node
  25. {
  26.     ll cost;
  27.     ll cnt;
  28.     node * to[2];
  29.     node()
  30.     {
  31.         cost = 0, cnt = 0;
  32.         to[0] = 0, to[1] = 0;
  33.     }
  34. };
  35.  
  36. const int digits_number = 32;
  37.  
  38.  
  39. inline unsigned rev(unsigned v)
  40. {
  41.     unsigned r = 0;
  42.  
  43.     for(int i = 0; i < digits_number; ++i)
  44.     {
  45.         r |= (v & 1) << (digits_number - 1 - i);
  46.         v >>= 1;
  47.     }
  48.     return r;
  49. }
  50.  
  51.  
  52. void add(node * root, unsigned cost, ll cnt)
  53. {
  54.     unsigned rev_cost = rev(cost);
  55.     ll add_cost = cnt * cost;
  56.     int it = digits_number;
  57.     while(it--)
  58.     {
  59.         root->cnt += cnt;
  60.         root->cost += add_cost;
  61.         if (!root->to[rev_cost & 1])
  62.             root->to[rev_cost & 1] = new node();
  63.         root = root->to[rev_cost & 1];
  64.         rev_cost >>= 1;
  65.     }
  66.     root->cost += add_cost;
  67.     root->cnt += cnt;
  68. }
  69.  
  70. inline ll Cnt(node * z)
  71. {
  72.     return z ? z->cnt : 0;
  73. }
  74.  
  75. inline ll Cost(node * z)
  76. {
  77.     return z ? z->cost : 0;
  78. }
  79.  
  80. ll GET(node * sell, node * buy)
  81. {
  82.     ll ans = 0;
  83.     ll sell_count = 0, buy_count = 0;
  84.     int it = digits_number;
  85.     unsigned cost = 0;
  86.     while(it--)
  87.     {
  88.         if (sell_count + Cnt(sell->to[0]) == buy_count + Cnt(buy->to[1]))
  89.         {
  90.             ans -= Cost(sell->to[0]) - Cost(buy->to[1]);
  91.             return ans;
  92.         }
  93.         if (sell_count + Cnt(sell->to[0]) < buy_count + Cnt(buy->to[1]))
  94.         {
  95.             ans -= Cost(sell->to[0]);
  96.             sell_count += Cnt(sell->to[0]);
  97.             sell = sell->to[1];
  98.             buy = buy->to[1];
  99.             cost = cost * 2 + 1;
  100.         }
  101.         else
  102.         {
  103.             ans += Cost(buy->to[1]);
  104.             buy_count += Cnt(buy->to[1]);
  105.             sell = sell->to[0];
  106.             buy = buy->to[0];
  107.             cost = cost * 2;
  108.         }
  109.     }
  110.     ans += (sell_count - buy_count) * cost;
  111.     return ans;
  112. }
  113.  
  114. struct query
  115. {
  116.     int type;
  117.     unsigned cost;
  118.     ll cnt;
  119. };
  120.  
  121. query nextQuery()
  122. {
  123.     string type;
  124.     cin >> type;
  125.     query res;
  126.     if (type[0] == 'e')
  127.         exit(0);
  128.     if (type[0] == 's')
  129.         res.type = 0;
  130.     else
  131.         res.type = 1;
  132.     cin >> res.cnt >> res.cost;
  133.     return res;
  134. }
  135.  
  136. int main()
  137. {
  138.     ios_base::sync_with_stdio(false);
  139.  
  140.     node * sell = new node();
  141.     node * buy = new node();
  142.  
  143.     while(1)
  144.     {
  145.         query Q = nextQuery();
  146.         if (Q.type == 0)
  147.         {
  148.             add(sell, Q.cost, Q.cnt);
  149.             add(buy, Q.cost, 0);
  150.         }
  151.         else
  152.         {
  153.             add(buy, Q.cost, Q.cnt);
  154.             add(sell, Q.cost, 0);
  155.         }
  156.         cout << GET(sell, buy) << endl;
  157.     }
  158.     return 0;
  159. }
  160.  
Runtime error #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
https://ideone.com/30A56a
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!