Advertisement
Guest User

Untitled

a guest
Jul 20th, 2018
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define fi first
  6. #define se second
  7. #define amen exit(0)
  8. #define endl "\n"
  9.  
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12.  
  13. typedef int ll;
  14. typedef pair <ll, ll> pii;
  15. typedef long double ld;
  16.  
  17. template <class type1>
  18. using super_set = tree <type1, null_type, less <type1>, rb_tree_tag, tree_order_statistics_node_update>;
  19. template <class type1, class type2>
  20. using super_map = tree <type1, type2, less <type1>, rb_tree_tag, tree_order_statistics_node_update>;
  21. #define tree nado_ubrat_tree_potomu_chto_tree_est_v_biblioteke_s_super_setom
  22.  
  23. const ll D = 200007;
  24. const ll Inf = 1000000107;
  25. const ll block = 3000;
  26.  
  27. vector <pii> a, additive;
  28. vector <ll> tree[4*D];
  29. ll n, m;
  30.  
  31. void combine(ll v)
  32. {
  33. tree[v].resize(tree[v*2 + 1].size() + tree[v*2 + 2].size());
  34. merge(tree[v*2 + 1].begin(), tree[v*2 + 1].end(),
  35. tree[v*2 + 2].begin(), tree[v*2 + 2].end(),
  36. tree[v].begin());
  37. }
  38.  
  39. void build_tree(ll v, ll sl, ll sr)
  40. {
  41. if (sl == sr)
  42. {
  43. tree[v].push_back(a[sl].se);
  44. return;
  45. }
  46. ll mid = (sl + sr) / 2;
  47. build_tree(v*2 + 1, sl, mid);
  48. build_tree(v*2 + 2, mid + 1, sr);
  49. combine(v);
  50. }
  51.  
  52. ll get(ll v, ll sl, ll sr, ll xl, ll yl, ll xr, ll yr)
  53. {
  54. if (xl > sr || xr < sl)
  55. return 0;
  56. if (xl <= sl && sr <= xr)
  57. return upper_bound(tree[v].begin(), tree[v].end(), yr) -
  58. lower_bound(tree[v].begin(), tree[v].end(), yl);
  59. ll mid = (sl + sr) / 2;
  60. return get(v*2 + 1, sl, mid, xl, yl, xr, yr) +
  61. get(v*2 + 2, mid + 1, sr, xl, yl, xr, yr);
  62. }
  63.  
  64. int main()
  65. {
  66. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  67.  
  68. ll x1, y1, x2, y2;
  69. cin >> n;
  70. for (ll i = 1; i <= n; i++)
  71. cin >> x1 >> y1, a.push_back({x1, y1});
  72. sort(a.begin(), a.end());
  73. build_tree(0, 0, n - 1);
  74.  
  75. char id;
  76. ll res = 0;
  77. cin >> m;
  78. for (ll i = 1; i <= m; i++)
  79. {
  80. cin >> id >> x1 >> y1;
  81. if (id == '?')
  82. {
  83. cin >> x2 >> y2;
  84. res = 0;
  85. for (pii val : additive)
  86. if (x1 <= val.fi && val.fi <= x2 && y1 <= val.se && val.se <= y2)
  87. res++;
  88. x1 = lower_bound(a.begin(), a.end(), (pii) {x1, 0}) - a.begin();
  89. x2 = lower_bound(a.begin(), a.end(), (pii) {x2 + 1, 0}) - a.begin() - 1;
  90. res += get(0, 0, a.size() - 1, x1, y1, x2, y2);
  91. cout << res << endl;
  92. }
  93. else
  94. {
  95. additive.push_back({x1 + res % 100, y1 + res % 101});
  96. if (additive.size() >= block)
  97. {
  98. for (pii val : additive)
  99. a.push_back(val);
  100. additive.clear();
  101. sort(a.begin(), a.end());
  102. build_tree(0, 0, a.size() - 1);
  103. }
  104. }
  105. }
  106. amen;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement