SHARE
TWEET

Untitled

a guest Dec 8th, 2019 69 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top