제출 #366028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366028		Kazalika	청소 (JOI20_sweeping)	C++14	11 / 100	18037 ms	127532 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 1e9 + 9;

int grand() {
  return ((ll)rand() << 15) + rand();
}

struct treap {
  int x, y, i;
  int set_x, set_y;
  int pr;
  treap *l, *r, *par;
  treap(int x, int y, int i) : x(x), y(y), i(i), set_x(-1), set_y(-1), pr(grand()), l(0), r(0), par(0) {}
  treap() {}
};

void upd(treap *t, int a, int b) {
  if (!t)
    return;
  if (a != -1)
    t->set_x = t->x = a;
  if (b != -1)
    t->set_y = t->y = b;
}

void push(treap *t) {
  upd(t->l, t->set_x, t->set_y);
  upd(t->r, t->set_x, t->set_y);
  t->set_x = t->set_y = -1;
}

void s_p(treap *t, treap *p) { if (t) t->par = p; }

pair<treap *, treap *> split(treap *t, pair<int, int> k, int i = inf) {
  if (!t)
    return {0, 0};
  push(t);
  if (t->x > k.first || t->y > k.second || (k == make_pair(t->x, t->y) && t->i == i)) {
    s_p(t->l, 0);
    auto a = split(t->l, k, i);
    t->l = a.second;
    s_p(t->l, t);
    return {a.first, t};
  } else {
    s_p(t->r, 0);
    auto a = split(t->r, k, i);
    t->r = a.first;
    s_p(t->r, t);
    return {t, a.second};
  }
}

treap *merge(treap *a, treap *b) {
  if (!a)
    return b;
  if (!b)
    return a;
  push(a), push(b);
  if (a->pr > b->pr) {
    s_p(a->r, 0);
    a->r = merge(a->r, b);
    s_p(a->r, a);
    return a;
  } else {
    s_p(b->l, 0);
    b->l = merge(a, b->l);
    s_p(b->l, b);
    return b;
  }
}

treap *wtf_merge(treap *a, treap *b) { // почему это работает быстро?
  if (!a)
    return b;
  if (!b)
    return a;
  push(a), push(b);
  if (a->pr < b->pr)
    swap(a, b);
  auto sb = split(b, {a->x, a->y}, a->i);
  s_p(a->l, 0), s_p(a->r, 0);
  a->l = wtf_merge(a->l, sb.first), a->r = wtf_merge(a->r, sb.second);
  s_p(a->l, a);
  s_p(a->r, a);
  return a;
}

pair<int, int> gl(treap *t) {
  push(t);
  if (t->l)
    return gl(t->l);
  return {t->x, t->y};
}

int n, m, q;

struct btreap {
  treap *gr;
  int x, y, mxy, pr;
  btreap *l, *r;
  btreap(treap *t) {
    gr = t;
    auto L = gl(t);
    x = L.first, y = n - L.second;
    mxy = y;
    pr = grand();
    l = r = 0;
  }
  btreap() {}
};

void upd(btreap *t) {
  if (!t)
    return;
  t->mxy = t->y;
  if (t->l)
    t->mxy = max(t->mxy, t->l->mxy);
  if (t->r)
    t->mxy = max(t->mxy, t->r->mxy);
}

pair<btreap *, btreap *> split(btreap *t, int k, treap *x, bool inc) {
  if (!t)
    return {0, 0};
  upd(t);
  if (t->x > k || (t->x == k && inc && t->gr > x)) {    // ???
    auto a = split(t->l, k, x, inc);
    t->l = a.second;
    upd(t);
    return {a.first, t};
  } else {
    auto a = split(t->r, k, x, inc);
    t->r = a.first;
    upd(t);
    return {t, a.second};
  }
}

btreap *merge(btreap *a, btreap *b) {
  if (!a)
    return b;
  if (!b)
    return a;
  if (a->pr > b->pr) {
    a->r = merge(a->r, b);
    upd(a);
    return a;
  } else {
   b->l = merge(a, b->l);
   upd(b);
   return b;
  }
}

btreap *insert_btreap(btreap *t, treap *x) {
  if (!x)
    return t;
  btreap *ins = new btreap(x);
  auto a = split(t, ins->x, x, true);
  a.first = merge(a.first, ins);
  return merge(a.first, a.second);
}

vector <treap *> trav;

btreap *traverse(btreap *t, int y) {    // x <= l, y <= n - l -> l <= n - y -> l <= y_in_treap
  if (!t || t->mxy < y)
    return t;
  if (t->y < y) {
    t->l = traverse(t->l, y);
    t->r = traverse(t->r, y);
    upd(t);
    return t;
  } else {
    trav.push_back(t->gr);   // нашли челика из поддерева которого надо вытащить ребят
    btreap *a = traverse(t->l, y);
    btreap *b = traverse(t->r, y);
    return merge(a, b);
  }
}

btreap *groups = 0;

void sweep(int l) {
  trav.clear();
  auto a = split(groups, l, 0, false);   // находим группы из которых нужно вытащить челиков
  groups = a.second;
  groups = merge(traverse(a.first, l), groups);
  for (auto &dust : trav) {
    auto x = split(dust, {l, n - l});
    dust = x.first;
    groups = insert_btreap(groups, x.second);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m >> q;
  vector<treap *> ptr;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    treap *ins = new treap(x, y, i);
    groups = insert_btreap(groups, ins);
    ptr.push_back(ins);
  }
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    if (t == 1) {
      int p;
      cin >> p;
      p--;
      treap *me = ptr[p];
      vector<treap *> way;
      while (me) {
        way.push_back(me);
        me = me->par;
      }
      for (int j = (int) way.size() - 1; j >= 0; --j)
        push(way[j]);
      cout << ptr[p]->x << ' ' << ptr[p]->y << '\n';
    } else if (t == 2) {
      int l;
      cin >> l;
      sweep(n - l);
      treap *new_gr = 0;
      for (auto dust : trav) {
        upd(dust, n - l, -1);
        new_gr = wtf_merge(new_gr, dust);
      }
      groups = insert_btreap(groups, new_gr);
    } else if (t == 3) {
      int l;
      cin >> l;
      sweep(l);
      treap *new_gr = 0;
      for (auto dust : trav) {
        upd(dust, -1, n - l);
        new_gr = wtf_merge(new_gr, dust);
      }
      groups = insert_btreap(groups, new_gr);
    } else {
      int x, y;
      cin >> x >> y;
      treap *ins = new treap(x, y, m);
      m++;
      groups = insert_btreap(groups, ins);
      ptr.push_back(ins);
    }
  }
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25