kdzhr

Untitled

Feb 23rd, 2021
490
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll sz(node *&t) {
  2.     return getCnt(t);
  3. }
  4.  
  5. void un(node *&t, int ind) {
  6.     auto[left, r] = split(t, ind);
  7.     auto[mid, right] = split(r, 2);
  8.     auto[f, s] = split(mid, 1);
  9.     auto nw = new node(getSum(f) + getSum(s));
  10.     t = merge(merge(left, nw), right);
  11. }
  12.  
  13. void sp(node *&t, int ind, ll cnt) {
  14.     auto[left, r] = split(t, ind);
  15.     auto[mid, right] = split(r, 1);
  16.     auto nw1 = new node(cnt);
  17.     auto nw2 = new node(getSum(mid) - cnt);
  18.     t = merge(merge(merge(left, nw1), nw2), right);
  19. }
  20.  
  21. void res(node *&t, int ind, ll cnt) {
  22.     auto[left, r] = split(t, ind);
  23.     auto[mid, right] = split(r, 1);
  24.     auto nw = new node(cnt);
  25.     t = merge(merge(left, nw), right);
  26. }
  27.  
  28. ll gc(node *&t, int cnt) {
  29.     auto[left, right] = split(t, cnt);
  30.     ll res = getCnt(left);
  31.     t = merge(left, right);
  32.     return res;
  33. }
  34.  
  35. void solve() {
  36.     int n;
  37.     std::cin >> n >> m;
  38.     node *t = nullptr;
  39.     for (int i = 0; i < n; ++i) {
  40.         int x;
  41.         std::cin >> x;
  42.         t = merge(t, new node(x));
  43.     }
  44.  
  45.     int q;
  46.     std::cin >> q;
  47.     for (int i = 0; i < q; ++i) {
  48.         std::string qs;
  49.         std::cin >> qs;
  50.         if (qs == "size") {
  51.             std::cout << sz(t) << '\n';
  52.         } else if (qs == "chapter") {
  53.             // бинпоиск
  54.             ll cnt;
  55.             std::cin >> cnt;
  56.             int left = 0, right = getSz(t);
  57.             while (right - left > 1) {
  58.                 int mid = (left + right) / 2;
  59.                 if (gc(t, mid) < cnt) {
  60.                     left = mid;
  61.                 } else {
  62.                     right = mid;
  63.                 }
  64.             }
  65.             std::cout << left + 1 << '\n';
  66.         } else if (qs == "union") {
  67.             int ind;
  68.             std::cin >> ind;
  69.             un(t, ind - 1);
  70.         } else if (qs == "split") {
  71.             int ind;
  72.             ll cnt;
  73.             std::cin >> ind >> cnt;
  74.             sp(t, ind - 1, cnt);
  75.         } else if (qs == "resize") {
  76.             int ind;
  77.             ll cnt;
  78.             std::cin >> ind >> cnt;
  79.             res(t, ind - 1, cnt);
  80.         }
  81.     }
  82. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×