fork(2) download
copy 
  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 int rdseed = (uint64_t)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
  14.  
  15. int hash_f(int x) { return ((x >> 16) ^ x) * 0x45d9f3b; }
  16.  
  17. struct chash {
  18.     int operator()(int x) const { return hash_f(x); }
  19. };
  20.  
  21. struct node;
  22. node *newNode();
  23.  
  24. struct node {
  25.     ll lv, rv, sum;
  26.     node *left, *right;
  27.  
  28.     node() : left(NULL), right(NULL), sum(0) {}
  29.  
  30.     inline void init(ll l, ll r) {
  31.         lv = l;
  32.         rv = r;
  33.     }
  34.  
  35.     inline void extend() {
  36.         if (!left) {
  37.             ll m = (lv + rv) / 2;
  38.             left = newNode();
  39.             right = newNode();
  40.             left->init(lv, m);
  41.             right->init(m + 1, rv);
  42.         }
  43.     }
  44.  
  45.     ll getSum(ll l, ll r) {
  46.         if (r < lv || rv < l) {
  47.             return 0;
  48.         }
  49.  
  50.         if (l <= lv && rv <= r) {
  51.             return sum;
  52.         }
  53.  
  54.         extend();
  55.         return left->getSum(l, r) + right->getSum(l, r);
  56.     }
  57.  
  58.     void update(ll p, ll newVal) {
  59.         if (lv == rv) {
  60.             sum = newVal;
  61.             return;
  62.         }
  63.  
  64.         extend();
  65.         (p <= left->rv ? left : right)->update(p, newVal);
  66.         sum = left->sum + right->sum;
  67.     }
  68. };
  69.  
  70. ll bufSize = 5e7;
  71. node buf[(int)5e7];
  72. node *newNode() { return &buf[--bufSize]; }
  73.  
  74. ll N = 1e9;
  75. ll NUM_ELEM = 2e5;
  76. ll NUM_QUERIES = 2e5;
  77.  
  78. gp_hash_table<ll, ll, chash> seg;
  79.  
  80. ll get(ll x) {
  81.     auto res = seg.find(x);
  82.     return (res == seg.end()) ? 0 : res->second;
  83.     // return (seg.find(x) == seg.end()) ? 0 : seg[x];
  84. }
  85. void modify(ll p, ll val) {
  86.     for (seg[p += N] = val; p > 0; p >>= 1) {
  87.         seg[p >> 1] = get(p) + get(p ^ 1);
  88.     }
  89. }
  90.  
  91. ll query(ll l, ll r) {
  92.     ll res = 0;
  93.     for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
  94.         if (l & 1)
  95.             res += get(l++);
  96.         if (r & 1)
  97.             res += get(--r);
  98.     }
  99.     return res;
  100. }
  101.  
  102. int main() {
  103.     ios::sync_with_stdio(0);
  104.     cin.tie(0);
  105.     vector<pii> elems;
  106.     for (ll i = 0; i < NUM_ELEM; i++) {
  107.         elems.push_back({uni(rng), uni(rng)});
  108.     }
  109.     vector<pii> queries;
  110.     for (ll i = 0; i < NUM_QUERIES; i++) {
  111.         ll a = uni(rng), b = uni(rng);
  112.         if (a > b)
  113.             swap(a, b);
  114.         queries.push_back({a, b});
  115.     }
  116.     vector<ll> ans1, ans2;
  117.     clock_t begin;
  118.     begin = clock();
  119.     for (auto i : elems) {
  120.         modify(i.first, i.second);
  121.     }
  122.     for (auto i : queries) {
  123.         ans2.push_back(query(i.first, i.second + 1));
  124.     }
  125.     cout << "policy hash: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  126.     seg.clear();
  127.     node *rmq = newNode();
  128.     rmq->init(0, 1e9);
  129.     begin = clock();
  130.     for (auto i : elems) {
  131.         rmq->update(i.first, i.second);
  132.     }
  133.     for (auto i : queries) {
  134.         ans1.push_back(rmq->getSum(i.first, i.second));
  135.     }
  136.     cout << "pointer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  137.  
  138.     for (int i = 0; i < ans1.size(); i++) {
  139.         assert(ans1[i] == ans2[i]);
  140.     }
  141. }
Success #stdin #stdout 1.51s 1974784KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
policy hash: 0.579694
pointer: 0.490162
https://ideone.com/bdSh9H
language:
C++14 (gcc 8.3)
created:
5 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!