結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー zimpha
提出日時 2019-05-23 03:25:16
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 211 ms / 2,000 ms
コード長 2,579 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 533 ms
コンパイル使用メモリ 67,324 KB
最終ジャッジ日時 2025-01-07 03:51:24
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:104:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  104 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:109:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  109 |       scanf("%d%d", &l, &r);
      |       ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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