Guest User

Untitled

a guest
Dec 8th, 2019
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. mt19937 rnd(time(nullptr));
  7.  
  8. const int INF = 1e9 + 7;
  9.  
  10. int n, q;
  11. vector <int> tree, add;
  12. set <pair <int, int> > all, all_inv;
  13. map <pair <int, int>, int> color;
  14.  
  15. void push(int v, int tl, int tr) {
  16. tree[v] += add[v] * (tr - tl);
  17. if (tl + 1 != tr) {
  18. add[v * 2] += add[v];
  19. add[v * 2 + 1] += add[v];
  20. }
  21. add[v] = 0;
  22. }
  23.  
  24. int get(int v, int tl, int tr, int l, int r) {
  25. push(v, tl, tr);
  26. if (l >= tr || tl >= r)
  27. return 0;
  28. else if (l <= tl && r >= tr)
  29. return tree[v];
  30. else {
  31. int tm = (tl + tr) / 2;
  32. auto kek = get(v * 2, tl, tm, l, r);
  33. auto lol = get(v * 2 + 1, tm, tr, l, r);
  34. return kek + lol;
  35. }
  36. }
  37.  
  38. void upd(int v, int tl, int tr, int l, int r, int delta) {
  39. push(v, tl, tr);
  40. if (l >= tr || tl >= r)
  41. return;
  42. else if (l <= tl && r >= tr) {
  43. add[v] += delta;
  44. push(v, tl, tr);
  45. }
  46. else {
  47. int tm = (tl + tr) / 2;
  48. upd(v * 2, tl, tm, l, r, delta);
  49. upd(v * 2 + 1, tm, tr, l, r, delta);
  50. tree[v] = tree[v * 2] + tree[v * 2 + 1];
  51. }
  52. }
  53.  
  54. int split(int mid, bool fl) {
  55. auto kek = *all_inv.lower_bound({-mid, -INF});
  56. int left = -kek.first, right = -kek.second;
  57. int c = color[{left, right}];
  58. if (fl) {
  59. if (mid != left) {
  60. all_inv.erase(kek);
  61. all.erase({left, right});
  62. all.insert({left, mid - 1});
  63. all_inv.insert({-left, -mid + 1});
  64. color[{left, mid - 1}] = c;
  65. color.erase(color.find({left, right}));
  66. }
  67. }
  68. else {
  69. if (mid != right) {
  70. all_inv.erase(kek);
  71. all.erase({left, right});
  72. all.insert({mid + 1, right});
  73. all_inv.insert({-mid - 1, -right});
  74. color[{mid + 1, right}] = c;
  75. color.erase(color.find({left, right}));
  76. }
  77. }
  78. return c;
  79. }
  80.  
  81. void change(int l, int r, int x) {
  82. auto lol = *all_inv.lower_bound({-l, -INF});
  83. if (-lol.first <= l && r <= -lol.second) {
  84. pair <int, int> kek = {-lol.first, -lol.second};
  85. all.erase(kek);
  86. all_inv.erase(lol);
  87. int c = color[kek];
  88. color.erase(kek);
  89. if (kek.first != l - 1) {
  90. all.insert({kek.first, l - 1});
  91. all_inv.insert({-kek.first, -l + 1});
  92. color[{kek.first, l - 1}] = c;
  93. }
  94. if (r != kek.second) {
  95. all.insert({r + 1, kek.second});
  96. all_inv.insert({-r - 1, -kek.second});
  97. color[{r + 1, kek.second}] = c;
  98. }
  99. all.insert({l, r});
  100. all_inv.insert({-l, -r});
  101. color[{l, r}] = x;
  102. upd(1, 0, n, l, r + 1, abs(x - c));
  103. return;
  104. }
  105. //cout << "aa" << endl;
  106. int c1 = split(l, true);
  107. int c2 = split(r, false);
  108. auto kek = *all.lower_bound({l, -INF});
  109. if (kek.first != l)
  110. upd(1, 0, n, l, kek.first, abs(c1 - x));
  111. kek = *all_inv.lower_bound({-r, -INF});
  112. int left = -kek.second;
  113. if (left != r)
  114. upd(1, 0, n, left + 1, r + 1, abs(c2 - x));
  115. pair <int, int> now = {INF, INF};
  116. if (all.lower_bound({l, -INF}) != all.end())
  117. now = *all.lower_bound({l, -INF});
  118. while (now.second <= r) {
  119. upd(1, 0, n, now.first, now.second + 1, abs(x - color[now]));
  120. all.erase(now);
  121. all_inv.erase({-now.first, -now.second});
  122. color.erase(color.find(now));
  123. if (all.lower_bound({now.second, -INF}) == all.end())
  124. break;
  125. now = *all.lower_bound({now.second, -INF});
  126. }
  127. all.insert({l, r});
  128. all_inv.insert({-l, -r});
  129. color[{l, r}] = x;
  130. }
  131.  
  132. int32_t main() {
  133. ios_base::sync_with_stdio(false);
  134. cin.tie(nullptr);
  135. cout.tie(nullptr);
  136. while (true) {
  137. //cin >> n >> q;
  138. n = rnd() % 6 + 1, q = rnd() % 6 + 1;
  139. tree.resize(4 * n);
  140. add.resize(4 * n);
  141. vector <int> num(n), smth(n);
  142. for (int i = 0; i < n; i++) {
  143. all.insert({i, i});
  144. all_inv.insert({-i, -i});
  145. color[{i, i}] = i;
  146. num[i] = i;
  147. }
  148. vector <int> ans1, ans2;
  149. vector <vector <int> > queries;
  150. while (q--) {
  151. int type;
  152. //cin >> type;
  153. type = rnd() % 2 + 1;
  154. if (type == 1) {
  155. int l, r, x;
  156. //cin >> l >> r >> x;
  157. l = rnd() % n + 1, r = rnd() % n + 1, x = rnd() % 7 + 1;
  158. if (l > r)
  159. swap(l, r);
  160. l--;
  161. r--;
  162. x--;
  163. change(l, r, x);
  164. for (int i = l; i <= r; i++) {
  165. smth[i] += abs(x - num[i]);
  166. num[i] = x;
  167. }
  168. queries.push_back({1, l + 1, r + 1, x});
  169. }
  170. else {
  171. int l, r;
  172. //cin >> l >> r;
  173. l = rnd() % n + 1, r = rnd() % n + 1;
  174. if (l > r)
  175. swap(l, r);
  176. l--;
  177. ans1.push_back(get(1, 0, n, l, r));
  178. int res = 0;
  179. for (int i = l; i < r; i++)
  180. res += smth[i];
  181. ans2.push_back(res);
  182. queries.push_back({2, l + 1, r + 1});
  183. }
  184. }
  185. for (int i = 0; i < (int)ans1.size(); i++) {
  186. if (ans1[i] != ans2[i]) {
  187. cout << n << " " << (int)queries.size() << "\n";
  188. for (auto el : queries) {
  189. for (auto elem : el)
  190. cout << elem << " ";
  191. cout << "\n";
  192. }
  193. return 0;
  194. }
  195. }
  196. cout << "OK" << endl;
  197. }
  198. return 0;
  199. }
RAW Paste Data