oj.uz

Submission #366028

# Submission time Handle Problem Language Result Execution time Memory
366028 2021-02-12T18:44:14 Z Kazalika Sweeping (JOI20_sweeping) C++14
11 / 100
 18000 ms 127532 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 876 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 8 ms 1004 KB Output is correct
5 Correct 11 ms 1132 KB Output is correct
6 Correct 99 ms 748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4557 ms 117268 KB Output is correct
2 Correct 4636 ms 127236 KB Output is correct
3 Correct 4484 ms 127532 KB Output is correct
4 Correct 3555 ms 108640 KB Output is correct
5 Correct 4414 ms 121288 KB Output is correct
6 Correct 4401 ms 118740 KB Output is correct
7 Correct 4549 ms 125144 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2252 ms 76664 KB Output is correct
2 Correct 1990 ms 90388 KB Output is correct
3 Correct 1471 ms 96492 KB Output is correct
4 Execution timed out 18037 ms 101220 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2252 ms 76664 KB Output is correct
2 Correct 1990 ms 90388 KB Output is correct
3 Correct 1471 ms 96492 KB Output is correct
4 Execution timed out 18037 ms 101220 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 876 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 8 ms 1004 KB Output is correct
5 Correct 11 ms 1132 KB Output is correct
6 Correct 99 ms 748 KB Output is correct
7 Correct 4557 ms 117268 KB Output is correct
8 Correct 4636 ms 127236 KB Output is correct
9 Correct 4484 ms 127532 KB Output is correct
10 Correct 3555 ms 108640 KB Output is correct
11 Correct 4414 ms 121288 KB Output is correct
12 Correct 4401 ms 118740 KB Output is correct
13 Correct 4549 ms 125144 KB Output is correct
14 Correct 2252 ms 76664 KB Output is correct
15 Correct 1990 ms 90388 KB Output is correct
16 Correct 1471 ms 96492 KB Output is correct
17 Execution timed out 18037 ms 101220 KB Time limit exceeded
18 Halted 0 ms 0 KB -