fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6.  
  7. typedef long long ll;
  8. random_device rd;
  9. mt19937 rng(0);
  10. uniform_int_distribution<ll> uni(1, 1e9);
  11. typedef pair<ll, ll> pii;
  12.  
  13. const ll rdseed = (uint64_t)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
  14.  
  15. unsigned hash_f(unsigned x) {
  16. x = ((x >> 16) ^ x) * 0x45d9f3b;
  17. x = ((x >> 16) ^ x) * 0x45d9f3b;
  18. x = (x >> 16) ^ x;
  19. return x;
  20. }
  21.  
  22. struct chash {
  23. ll operator()(ll x) const { return hash_f(x); }
  24. };
  25.  
  26. const ll N = 1e18;
  27. const ll NUM_ELEM = 2e5;
  28. const ll NUM_QUERIES = 2e5;
  29. struct Node {
  30. Node *lp, *rp;
  31. ll sum;
  32. };
  33. inline ll eval(Node *p) { return p ? p->sum : 0LL; }
  34.  
  35. const ll bufSize = NUM_ELEM * 31;
  36. Node buf[bufSize];
  37. Node *newNode() {
  38. static auto ptr = buf;
  39. return ptr++;
  40. }
  41.  
  42. ll getSum(Node *cur, ll l, ll r, ll x, ll y) {
  43. if (!cur || x > r || y < l)
  44. return 0;
  45. if (x <= l && r <= y) {
  46. return cur->sum;
  47. }
  48. ll m = (l + r) / 2;
  49. return getSum(cur->lp, l, m, x, y) + getSum(cur->rp, m + 1, r, x, y);
  50. }
  51. void update(Node *&cur, ll l, ll r, ll pos, ll val) {
  52. if (!cur)
  53. cur = newNode();
  54. if (l == r) {
  55. cur->sum = val;
  56. } else {
  57. ll m = (l + r) / 2;
  58. if (pos <= m) {
  59. update(cur->lp, l, m, pos, val);
  60. } else {
  61. update(cur->rp, m + 1, r, pos, val);
  62. }
  63. cur->sum = eval(cur->lp) + eval(cur->rp);
  64. }
  65. }
  66. Node *root;
  67.  
  68. gp_hash_table<ll, ll, chash> seg;
  69.  
  70. ll get(ll x) {
  71. auto res = seg.find(x);
  72. return (res == seg.end()) ? 0 : res->second;
  73. // return (seg.find(x) == seg.end()) ? 0 : seg[x];
  74. }
  75. void modify(ll p, ll val) {
  76. for (seg[p += N] = val; p > 0; p >>= 1) {
  77. seg[p >> 1] = get(p) + get(p ^ 1);
  78. }
  79. }
  80.  
  81. ll query(ll l, ll r) {
  82. ll res = 0;
  83. for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
  84. if (l & 1)
  85. res += get(l++);
  86. if (r & 1)
  87. res += get(--r);
  88. }
  89. return res;
  90. }
  91.  
  92. signed main() {
  93. ios::sync_with_stdio(0);
  94. cin.tie(0);
  95. vector<pii> elems;
  96. for (ll i = 0; i < NUM_ELEM; i++) {
  97. elems.push_back({uni(rng), uni(rng)});
  98. }
  99. vector<pii> queries;
  100. for (ll i = 0; i < NUM_QUERIES; i++) {
  101. ll a = uni(rng), b = uni(rng);
  102. if (a > b)
  103. swap(a, b);
  104. queries.push_back({a, b});
  105. }
  106. vector<ll> ans1, ans2;
  107. clock_t begin;
  108. Node *rmq = newNode();
  109. begin = clock();
  110. for (auto i : elems) {
  111. modify(i.first, i.second);
  112. }
  113. for (auto i : queries) {
  114. ans2.push_back(query(i.first, i.second + 1));
  115. }
  116. cout << "policy hash: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  117. seg.clear();
  118.  
  119. begin = clock();
  120. for (auto i : elems) {
  121. update(root, 1, N, i.first, i.second);
  122. }
  123. for (auto i : queries) {
  124. ans1.push_back(getSum(root, 1, N, i.first, i.second));
  125. }
  126. cout << "pointer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  127. for (ll i = 0; i < ans1.size(); i++) {
  128. assert(ans1[i] == ans2[i]);
  129. }
  130. }
Success #stdin #stdout 1.15s 166848KB
stdin
Standard input is empty
stdout
policy hash: 0.716413
pointer: 0.335393