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