Submission #217963

#	Time	Username	Problem	Language	Result	Execution time	Memory
217963		300iq	Sweeping (JOI20_sweeping)	C++17	100 / 100	6110 ms	161188 KiB

sweeping

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

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

void upd(treap *t, int a, int b) {
  if (!t) return;
  if (a != -1) {
    t->set_x = a;
    t->x = a;
  }
  if (b != -1) {
    t->set_y = b;
    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 set_par(treap *t, treap *p) {
  if (!t) return;
  t->par = p;
}

const int inf = 1e9;

pair <treap *, treap *> split(treap *t, pair <int, int> x, int id = inf) {
  if (!t) {
    return {0, 0};
  }
  if (t->x > x.first || t->y > x.second || (make_pair(t->x, t->y) == x && t->i > id)) {
    push(t);
    set_par(t->l, 0);
    auto a = split(t->l, x, id);
    t->l = a.second;
    set_par(t->l, t);
    return {a.first, t};
  } else {
    push(t);
    set_par(t->r, 0);
    auto a = split(t->r, x, id);
    t->r = a.first;
    set_par(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->prior > b->prior) {
    set_par(a->r, 0);
    a->r = merge(a->r, b);
    set_par(a->r, a);
    return a;
  } else {
    set_par(b->l, 0);
    b->l = merge(a, b->l);
    set_par(b->l, b);
    return b;
  }
}

treap *super_merge(treap *a, treap *b) {
  if (!a) return b;
  if (!b) return a;
  push(a), push(b);
  if (a->prior < b->prior) swap(a, b);
  auto t = split(b, make_pair(a->x, a->y), a->i);
  set_par(a->l, 0);
  set_par(a->r, 0);
  a->l = super_merge(a->l, t.first);
  a->r = super_merge(a->r, t.second);
  set_par(a->l, a);
  set_par(a->r, a);
  return a;
}

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

int n;

struct bst {
  treap *group;
  int my_l, my_r;
  int max_r;
  int prior;
  bst *l, *r;
  bst(treap *grou) {
    group = grou;
    auto ok = leftmost(group);
    my_l = ok.first;
    my_r = n - ok.second;
    max_r = my_r;
    prior = rnd();
    l = r = 0;
  }
  bst() {
  }
};

void recalc(bst *t) {
  if (!t) return;
  t->max_r = t->my_r;
  if (t->l) {
    t->max_r = max(t->max_r, t->l->max_r);
  }
  if (t->r) {
    t->max_r = max(t->max_r, t->r->max_r);
  }
}

pair <bst *, bst *> split(bst *t, int x, treap *gr, bool fl = true) {
  if (!t) return {0, 0};
  recalc(t);
  if (t->my_l > x || (fl && t->my_l == x && t->group > gr)) {
    auto a = split(t->l, x, gr, fl);
    t->l = a.second;
    recalc(t);
    return {a.first, t};
  } else {
    auto a = split(t->r, x, gr, fl);
    t->r = a.first;
    recalc(t);
    return {t, a.second};
  }
}

bst *merge(bst *a, bst *b) {
  if (!a) return b;
  if (!b) return a;
  if (a->prior > b->prior) {
    a->r = merge(a->r, b);
    recalc(a);
    return a;
  } else {
    b->l = merge(a, b->l);
    recalc(b);
    return b;
  }
}

bst *add(bst *t, treap *gr) {
  if (!gr) return t;
  bst *md = new bst(gr);
  auto a = split(t, md->my_l, gr);
  a.first = merge(a.first, md);
  return merge(a.first, a.second);
}

vector <treap*> guys;

bst *roll(bst *t, int r) {
  if (!t || t->max_r < r) return t;
  if (t->my_r < r) {
    t->l = roll(t->l, r);
    t->r = roll(t->r, r);
    recalc(t);
    return t;
  } else {
    guys.push_back(t->group);
    bst *a = roll(t->l, r);
    bst *b = roll(t->r, r);
    return merge(a, b);
  }
}


bst *groups = 0;

void flex(int l) {
  guys.clear();
  auto a = split(groups, l, 0, 0);
  groups = a.second;
  groups = merge(roll(a.first, l), groups);
  for (auto &c : guys) {
    auto x = split(c, make_pair(l, n - l));
    c = x.first;
    groups = add(groups, x.second);
  }
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int m, q;
  cin >> n >> m >> q;
  vector <treap*> ptrs;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    treap *go = new treap(x, y, i);
    groups = add(groups, go);
    ptrs.push_back(go);
  }
  for (int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int p;
      cin >> p;
      p--;
      treap *me = ptrs[p];
      vector <treap*> mda;
      while (me) {
        mda.push_back(me);
        me = me->par;
      }
      for (int i = (int) mda.size() - 1; i >= 0; i--) {
        push(mda[i]);
      }
      cout << ptrs[p]->x << ' ' << ptrs[p]->y << '\n';
    } else if (t == 2) {
      int l;
      cin >> l;
      guys.clear();
      flex(n - l);
      treap *cur_group = 0;
      for (auto c : guys) {
        upd(c, n - l, -1);
        cur_group = super_merge(cur_group, c);
      }
      groups = add(groups, cur_group);
    } else if (t == 3) {
      int l;
      cin >> l;
      guys.clear();
      flex(l);
      treap *cur_group = 0;
      for (auto c : guys) {
        upd(c, -1, n - l);
        cur_group = super_merge(cur_group, c);
      }
      groups = add(groups, cur_group);
    } else {
      int x, y;
      cin >> x >> y;
      treap *go = new treap(x, y, m);
      m++;
      groups = add(groups, go);
      ptrs.push_back(go);
    }
  }
}

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