結果

問題 No.686 Uncertain LIS
ユーザー zimphazimpha
提出日時 2019-05-23 03:25:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 226 ms / 2,000 ms
コード長 2,579 bytes
コンパイル時間 591 ms
コンパイル使用メモリ 71,432 KB
実行使用メモリ 7,776 KB
最終ジャッジ日時 2024-09-17 09:41:52
合計ジャッジ時間 6,444 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 191 ms
6,940 KB
testcase_10 AC 184 ms
7,164 KB
testcase_11 AC 116 ms
6,944 KB
testcase_12 AC 5 ms
6,940 KB
testcase_13 AC 58 ms
6,940 KB
testcase_14 AC 81 ms
6,944 KB
testcase_15 AC 53 ms
6,940 KB
testcase_16 AC 143 ms
6,940 KB
testcase_17 AC 225 ms
6,944 KB
testcase_18 AC 219 ms
6,948 KB
testcase_19 AC 224 ms
7,192 KB
testcase_20 AC 192 ms
6,944 KB
testcase_21 AC 192 ms
7,468 KB
testcase_22 AC 132 ms
6,940 KB
testcase_23 AC 133 ms
7,728 KB
testcase_24 AC 118 ms
6,944 KB
testcase_25 AC 118 ms
6,940 KB
testcase_26 AC 128 ms
7,236 KB
testcase_27 AC 126 ms
7,776 KB
testcase_28 AC 125 ms
7,180 KB
testcase_29 AC 126 ms
7,764 KB
testcase_30 AC 125 ms
6,944 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 157 ms
7,568 KB
testcase_33 AC 127 ms
6,944 KB
testcase_34 AC 226 ms
6,940 KB
testcase_35 AC 220 ms
7,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <functional>
#include <algorithm>

const int N = 3e5 + 10;
const int inf = 1e9 + 7;

struct node_t {
  node_t *l, *r;
  int size, value, add;
  node_t() = default;
  node_t(int v): l(0), r(0), size(1), value(v), add(0) {}
  node_t* update() {
    size = 1;
    if (l) size += l->size;
    if (r) size += r->size;
    return this;
  }
  void mark(int v) {
    value += v;
    add += v;
  }
  void push() {
    if (add) {
      if (l) l->mark(add);
      if (r) r->mark(add);
      add = 0;
    }
  }
} nodes[N];

node_t* build(node_t* l, node_t *r) {
  node_t* m = l + (r - l) / 2;
  if (l < m) m->l = build(l, m - 1);
  if (m < r) m->r = build(m + 1, r);
  m->update();
  return m;
}

int get_size(node_t *o) {
  return o ? o->size : 0;
}

bool random(int a, int b) {
  return rand() % (a + b) < a;
}

std::pair<node_t*, node_t*> split_by_value(node_t *o, int v) {//[-inf, v), [v, +inf)
  node_t *l = 0, *r = 0;
  if (!o) return {l, r};
  o->push();
  if (o->value < v) {
    std::tie(o->r, r) = split_by_value(o->r, v);
    l = o;
  } else {
    std::tie(l, o->l) = split_by_value(o->l, v);
    r = o;
  }
  o->update();
  return {l, r};
}

std::pair<node_t*, node_t*> split_by_size(node_t *o, int size) {//[0, size), [size, +inf)
  node_t *l = 0, *r = 0;
  if (!o) return {l, r};
  o->push();
  int ls = get_size(o->l);
  if (ls < size) {
    std::tie(o->r, r) = split_by_size(o->r, size - ls - 1);
    l = o;
  } else {
    std::tie(l, o->l) = split_by_size(o->l, size);
    r = o;
  }
  o->update();
  return {l, r};
}

node_t* merge(node_t *l, node_t *r) {
  if (!l || !r) return l ? l : r;
  l->push(); r->push();
  if (random(l->size, r->size)) {
    l->r = merge(l->r, r);
    return l->update();
  } else {
    r->l = merge(l, r->l);
    return r->update();
  }
}

void print(node_t *o) {
  if (!o) return;
  o->push();
  print(o->l);
  printf("%d ", o->value);
  print(o->r);
}

int main() {
  int T;
  T = 1;
  for (int cas = 1; cas <= T; ++cas) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= n; ++i) nodes[i] = node_t(inf);
    node_t* root = build(nodes, nodes + n + 1);
    for (int i = 0; i < n; ++i) {
      int l, r;
      scanf("%d%d", &l, &r);
      node_t *a, *b, *c, *d;
      std::tie(b, d) = split_by_value(root, r);
      std::tie(a, b) = split_by_value(b, l);
      std::tie(c, d) = split_by_size(d, 1);
      c->value = l;
      if (b) b->mark(1);
      root = merge(merge(a, c), merge(b, d));
    }
    node_t *x, *y;
    std::tie(x, y) = split_by_value(root, inf);
    printf("%d\n", x->size);
  }
  return 0;
}
0