Advertisement
Guest User

Untitled

a guest
May 23rd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. /**
  2. * Problem: segtree
  3. * Correct solution (must be OK).
  4. * Author: stgatilov
  5. * Solution: Build tree with sets of segments in it
  6. * Time: avg O(N log N) with O(N) memory
  7. */
  8.  
  9. //#pragma comment(linker, "/STACK:20000000")
  10. #include <vector>
  11. #include <list>
  12. #include <map>
  13. #include <set>
  14. #include <deque>
  15. #include <stack>
  16. #include <bitset>
  17. #include <algorithm>
  18. #include <functional>
  19. #include <numeric>
  20. #include <utility>
  21. #include <sstream>
  22. #include <iostream>
  23. #include <iomanip>
  24. #include <cstdio>
  25. #include <cmath>
  26. #include <cstring>
  27. #include <cassert>
  28. #include <cstdlib>
  29. #include <ctime>
  30. #include <cstdint>
  31. #include <unordered_set>
  32. #include <cinttypes>
  33. #include <array>
  34. #include <memory>
  35.  
  36. using namespace std;
  37. typedef long long int64;
  38. #ifdef HOME
  39. #define E(c) cerr<<#c
  40. #define Eo(x) cerr<<#x<<" = "<<(x)<<endl
  41. #define Ef(...) fprintf(stderr, __VA_ARGS__)
  42. #else
  43. #define E(c) ((void)0)
  44. #define Eo(x) ((void)0)
  45. #define Ef(...) ((void)0)
  46. #endif
  47.  
  48. #define SHIFT
  49. const int64 MULT = 1000000;
  50. const int BLOCK = 32;
  51.  
  52. typedef vector<int> idxList;
  53. struct Segment {
  54. int64 l, r;
  55. };
  56.  
  57. int n;
  58. int64 m;
  59. vector<Segment> arr;
  60. int h;
  61. vector<vector<idxList>> tree;
  62. int statCells, statChecks, statFound;
  63.  
  64. int64 Width(int lvl) {
  65. return ((BLOCK * MULT) << lvl);
  66. }
  67.  
  68. int GetLevel(int64 len) {
  69. int lvl = 0;
  70. while (Width(lvl) < len)
  71. lvl++;
  72. return lvl;
  73. }
  74.  
  75. int AddSegment(const Segment &seg) {
  76. int lvl = GetLevel(seg.r - seg.l);
  77. int64 wid = Width(lvl);
  78. int li = seg.l / wid;
  79. int ri = (seg.r + wid-1) / wid;
  80.  
  81. int id = arr.size();
  82. arr.push_back(seg);
  83.  
  84. for (int i = li; i < ri; i++)
  85. tree[lvl][i].push_back(id);
  86. return id;
  87. }
  88.  
  89. void FindSegments(int64 where, int &sum, int &cnt) {
  90. sum = cnt = 0;
  91.  
  92. for (int lvl = 0; lvl <= h; lvl++) {
  93. const auto &row = tree[lvl];
  94. int64 wid = Width(lvl);
  95. int cell = where / wid;
  96. statCells++;
  97. for (int id : row[cell]) {
  98. statChecks++;
  99. if (arr[id].l <= where && where < arr[id].r) {
  100. sum += id;
  101. cnt++;
  102. }
  103. }
  104. }
  105. statFound += cnt;
  106. }
  107.  
  108. void Init(int n) {
  109. ::n = n;
  110. ::m = n * MULT;
  111. ::h = 0;
  112. while (Width(h) < m + 16)
  113. h++;
  114. arr.reserve(n);
  115.  
  116. tree.resize(h + 1);
  117. for (int lvl = 0; lvl <= h; lvl++) {
  118. int64 wid = Width(lvl);
  119. int k = (m + wid-1) / wid;
  120. tree[lvl].resize(k);
  121. }
  122. }
  123.  
  124.  
  125. int main(int argc, char **argv) {
  126. freopen("input.txt", "r", stdin);
  127. freopen("output.txt", "w", stdout);
  128.  
  129. scanf("%d", &n);
  130. Init(n);
  131.  
  132. int64 shift = 0;
  133. for (int i = 0; i < 2*n; i++) {
  134. int t;
  135. scanf("%d", &t);
  136.  
  137. if (t == 0) {
  138. double rCtr, rRad;
  139. scanf("%lf%lf", &rCtr, &rRad);
  140. int64 ctr = int64(MULT * rCtr + 0.5);
  141. int64 rad = int64(MULT * rRad + 0.5);
  142. ctr = (ctr + shift) % m;
  143. Segment seg = {max(ctr - rad, 0LL), min(ctr + rad + 1, m)};
  144. AddSegment(seg);
  145. }
  146. else {
  147. double rWhere;
  148. scanf("%lf", &rWhere);
  149. int64 where = int64(MULT * rWhere + 0.5);
  150. where = (where + shift) % m;
  151. int sum, cnt;
  152. FindSegments(where, sum, cnt);
  153. #ifdef SHIFT
  154. shift = (shift + sum * MULT) % m;
  155. #else
  156. printf("[%d] ", sum);
  157. #endif
  158. printf("%d\n", cnt);
  159. }
  160. }
  161.  
  162. Ef("cells: %d; found: %d/%d\n", statCells, statFound, statChecks);
  163.  
  164. return 0;
  165. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement