Advertisement
ke_timofeeva7

Untitled

Jul 30th, 2023
28
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <set>
  7. #include <map>
  8. #include <unordered_set>
  9. #include <unordered_map>
  10. #include <stack>
  11. #include <queue>
  12. #include <deque>
  13. #include <ctime>
  14. #include <random>
  15. #include <cassert>
  16. #include <memory.h>
  17. #include <chrono>
  18. #define pii pair<int, int>
  19. #define pb push_back
  20. #define all(v) v.begin(), v.end()
  21. #define rall(v) v.rbegin(), v.rend()
  22. #define endl '\n'
  23. using namespace std;
  24.  
  25. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  26.  
  27. const long long INF = (long long)(1e9) + 7;
  28. const double EPS = 0.00000000001;
  29. const long long N = 1000001, R = 1LL << 19, ABC = 26, Logn = 20, MOD = 1e9;
  30.  
  31. struct Node {
  32. int sum;
  33. Node *left = nullptr, *right = nullptr;
  34. Node(int a) : sum(a) {}
  35. Node() : sum(0) {}
  36. };
  37.  
  38. Node* build(Node* root, int l, int r) {
  39. if (l == r) {
  40. root->sum = 0;
  41. return root;
  42. }
  43. root->left = new Node;
  44. root->right = new Node;
  45. int m = (l + r) / 2;
  46. root->left = build(root->left, l, m);
  47. root->right = build(root->right, m + 1, r);
  48. root->sum = root->left->sum + root->right->sum;
  49. return root;
  50. }
  51.  
  52. Node* push(Node* root) {
  53. root->left = new Node(*root->left);
  54. root->right = new Node(*root->right);
  55. return root;
  56. }
  57.  
  58. void update(Node* root, int nl, int nr, int idx) {
  59. if (idx == nl && idx == nr) {
  60. root->sum++;
  61. return;
  62. }
  63. root = push(root);
  64. int nm = (nl + nr) / 2;
  65. if (nm < idx)
  66. update(root->right, nm + 1, nr, idx);
  67. else
  68. update(root->left, nl, nm, idx);
  69. root->sum = root->left->sum + root->right->sum;
  70. }
  71.  
  72. int get(Node* rootl, Node* rootr, int nl, int nr, int k) {
  73. if (nl == nr) {
  74. return nl;
  75. }
  76. int nm = (nl + nr) / 2;
  77. if (rootr->left->sum - rootl->left->sum >= k)
  78. return get(rootl->left, rootr->left, nl, nm, k);
  79. else
  80. return get(rootl->right, rootr->right, nm + 1, nr, k - (rootr->left->sum - rootl->left->sum));
  81. }
  82. signed main() {
  83. ios_base::sync_with_stdio(0);
  84. cin.tie(0);
  85. cout.tie(0);
  86. cout.precision(17);
  87. srand(time(0));
  88.  
  89. long long n, l, m;
  90. cin >> n;
  91. vector<long long> vc(n + 1);
  92. cin >> vc[1] >> l >> m;
  93. for (int i = 2; i <= n; i++) {
  94. vc[i] = (vc[i - 1] * l + m) % MOD;
  95. }
  96. vector<long long> a;
  97. a = vc;
  98. sort(all(a));
  99. a.erase(unique(all(a)), a.end());
  100. for (int i = 0; i <= n; i++) {
  101. vc[i] = (long long)(lower_bound(all(a), vc[i]) - a.begin());
  102. }
  103. int b;
  104. cin >> b;
  105. vector<Node*> roots(1, new Node);
  106. roots[0] = build(roots[0], 0, R - 1);
  107. for (int i = 1; i <= n; i++) {
  108. roots.push_back(new Node(*roots.back()));
  109. update(roots.back(), 0, R - 1, vc[i]);
  110. }
  111. long long ans = 0;
  112. for (int i = 0; i < b; i++) {
  113. int g;
  114. cin >> g;
  115. long long x1, lx, mx, y1, ly, my;
  116. cin >> x1 >> lx >> mx >> y1 >> ly >> my;
  117. long long k1, lk, mk;
  118. cin >> k1 >> lk >> mk;
  119. long long left = min(x1, y1), right = max(x1, y1);
  120. //cout << get(roots[left-1], roots[right], 0, R - 1, k1) << endl;
  121. ans += a[get(roots[left - 1], roots[right], 0, R - 1, k1)];
  122. long long kg = k1;
  123. for (int j = 1; j < g; j++) {
  124. long long xg = ((left - 1) * lx + mx) % n + 1;
  125. long long yg = ((right - 1) * ly + my) % n + 1;
  126. left = min(xg, yg);
  127. right = max(xg, yg);
  128. kg = (((kg - 1) * lk + mk) % (right - left + 1)) + 1;
  129. //cout << get(roots[left - 1], roots[right], 0, R - 1, kg) << endl;
  130. ans += a[get(roots[left - 1], roots[right], 0, R - 1, kg)];
  131. }
  132. }
  133. cout << ans;
  134. return 0;
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement