oj.uz

Submission #217963

# Submission time Handle Problem Language Result Execution time Memory
217963 2020-03-31T11:13:47 Z 300iq Sweeping (JOI20_sweeping) C++17
100 / 100
 6110 ms 161188 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 9 ms 896 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 14 ms 1152 KB Output is correct
6 Correct 9 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4173 ms 121364 KB Output is correct
2 Correct 4160 ms 137696 KB Output is correct
3 Correct 4125 ms 137936 KB Output is correct
4 Correct 3164 ms 112092 KB Output is correct
5 Correct 3901 ms 128060 KB Output is correct
6 Correct 3838 ms 125496 KB Output is correct
7 Correct 4224 ms 135272 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 96604 KB Output is correct
2 Correct 1856 ms 73860 KB Output is correct
3 Correct 1281 ms 84060 KB Output is correct
4 Correct 2489 ms 103840 KB Output is correct
5 Correct 1948 ms 78992 KB Output is correct
6 Correct 1880 ms 72808 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 96604 KB Output is correct
2 Correct 1856 ms 73860 KB Output is correct
3 Correct 1281 ms 84060 KB Output is correct
4 Correct 2489 ms 103840 KB Output is correct
5 Correct 1948 ms 78992 KB Output is correct
6 Correct 1880 ms 72808 KB Output is correct
7 Correct 3392 ms 85484 KB Output is correct
8 Correct 3403 ms 85600 KB Output is correct
9 Correct 3366 ms 85588 KB Output is correct
10 Correct 2529 ms 83024 KB Output is correct
11 Correct 5278 ms 110300 KB Output is correct
12 Correct 3085 ms 75520 KB Output is correct
13 Correct 3324 ms 76732 KB Output is correct
14 Correct 190 ms 27768 KB Output is correct
15 Correct 1608 ms 84772 KB Output is correct
16 Correct 3296 ms 90872 KB Output is correct
17 Correct 3134 ms 87676 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 9 ms 896 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 14 ms 1152 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 4173 ms 121364 KB Output is correct
8 Correct 4160 ms 137696 KB Output is correct
9 Correct 4125 ms 137936 KB Output is correct
10 Correct 3164 ms 112092 KB Output is correct
11 Correct 3901 ms 128060 KB Output is correct
12 Correct 3838 ms 125496 KB Output is correct
13 Correct 4224 ms 135272 KB Output is correct
14 Correct 2060 ms 96604 KB Output is correct
15 Correct 1856 ms 73860 KB Output is correct
16 Correct 1281 ms 84060 KB Output is correct
17 Correct 2489 ms 103840 KB Output is correct
18 Correct 1948 ms 78992 KB Output is correct
19 Correct 1880 ms 72808 KB Output is correct
20 Correct 3392 ms 85484 KB Output is correct
21 Correct 3403 ms 85600 KB Output is correct
22 Correct 3366 ms 85588 KB Output is correct
23 Correct 2529 ms 83024 KB Output is correct
24 Correct 5278 ms 110300 KB Output is correct
25 Correct 3085 ms 75520 KB Output is correct
26 Correct 3324 ms 76732 KB Output is correct
27 Correct 190 ms 27768 KB Output is correct
28 Correct 1608 ms 84772 KB Output is correct
29 Correct 3296 ms 90872 KB Output is correct
30 Correct 3134 ms 87676 KB Output is correct
31 Correct 2979 ms 114656 KB Output is correct
32 Correct 4078 ms 130000 KB Output is correct
33 Correct 2564 ms 101716 KB Output is correct
34 Correct 5390 ms 161188 KB Output is correct
35 Correct 5381 ms 161044 KB Output is correct
36 Correct 2821 ms 104660 KB Output is correct
37 Correct 6110 ms 150528 KB Output is correct
38 Correct 4235 ms 132568 KB Output is correct
39 Correct 4215 ms 113536 KB Output is correct
40 Correct 3931 ms 124144 KB Output is correct