結果

問題 No.833 かっこいい電車
ユーザー akakimidoriakakimidori
提出日時 2019-05-24 22:07:37
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 4,350 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 34,176 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 03:42:21
合計ジャッジ時間 3,799 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
5,248 KB
testcase_01 WA -
testcase_02 AC 1 ms
5,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 WA -
testcase_07 RE -
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 RE -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 9 ms
5,376 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 70 ms
5,376 KB
testcase_31 AC 43 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

typedef struct WBT_node {
  i32 val;
  i32 size;
  struct WBT_node *left;
  struct WBT_node *right;
} node;

i32 get_size (const node *t) {
  return t == NULL ? 0 : t->size;
}

node *free_list = NULL;
node* new_node (const i32 val) {
  node *t = free_list;
  free_list = free_list->right;
  *t = (node) {val, 1, NULL, NULL};
  return t;
}

void free_node (node *t) {
  if (t == NULL) return;
  free_node (t->left);
  free_node (t->right);
  t->right = free_list;
  free_list = t;
}

void update (node *t) {
  if (t == NULL) return;
  t->size = 1 + get_size (t->left) + get_size (t->right);
}

i32 get_bias (node *t, i32 b) {
  if (t == NULL) return 0;
  i32 l = get_size (t->left) + 1;
  i32 r = get_size (t->right) + 1;
  if (b * l >= r && l <= b * r) return 0;
  return b * l < r ? -1 : 1;
}

node* left_rotate (node *u) {
  node *v = u->right;
  u->right = v->left;
  v->left = u;
  update (u);
  update (v);
  return v;
}

node* right_rotate (node *v) {
  node *u = v->left;
  v->left = u->right;
  u->right = v;
  update (v);
  update (u);
  return u;
}

node* balance (node *t) {
  i32 b = get_bias (t, 3);
  if (b < 0) {
    if (get_bias (t->right, 2) > 0) t->right = right_rotate (t->right);
    t = left_rotate (t);
  } else if (b > 0) {
    if (get_bias (t->left, 2) < 0) t->left = left_rotate (t->left);
    t = right_rotate (t);
  }
  return t;
}

node* join (node *l, node *m, node *r) {
  i32 a = get_size (l) + 1;
  i32 b = get_size (r) + 1;
  if (3 * a >= b && a <= 3 * b) {
    m->left = l;
    m->right = r;
    update (m);
    return m;
  }
  if (3 * a < b) {
    r->left = join (l, m, r->left);
    update (r);
    return balance (r);
  } else {
    l->right = join (l->right, m, r);
    update (l);
    return balance (l);
  }
}

node* merge (node *l, node *r) {
  if (l == NULL) return r;
  if (r == NULL) return l;
  if (get_size (l) <= get_size (r)) {
    r->left = merge (l, r->left);
    update (r);
    return balance (r);
  } else {
    l->right = merge (l->right, r);
    update (l);
    return balance (l);
  }
}

void split (node *t, i32 val, node **x, node **y) {
  if (t == NULL) return;
  if (t->val <= val) {
    split (t->right, val, x, y);
    *x = join (t->left, t, *x);
  } else {
    split (t->left, val, x, y);
    *y = join (*y, t, t->right);
  }
}

i32 find_max (node *t) {
  if (t == NULL) return -1;
  while (t->right != NULL) t = t->right;
  return t->val;
}

i32 find_min (node *t) {
  if (t == NULL) return 1000000;
  while (t->left != NULL) t = t->left;
  return t->val;
}

void add (i64 *bit, i32 x, i32 v) {
  i32 n = bit[0];
  for (i32 i = x; i <= n; i += i & -i) {
    bit[i] += v;
  }
}

i64 get_sum (i64 *bit, i32 x) {
  i64 sum = 0;
  for (i32 i = x; i > 0; i -= i & -i) {
    sum += bit[i];
  }
  return sum;
}

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void run (void) {
  i32 n, q;
  scanf ("%" SCNi32 "%" SCNi32, &n, &q);
  free_list = (node *) calloc (n + 1, sizeof (node));
  for (i32 i = 0; i + 1 < n + 1; ++i) {
    free_list[i].right = free_list + i + 1;
  }
  node *set = NULL;
  i64 *bit = (i64 *) calloc (n + 1, sizeof (i64));
  bit[0] = n;
  for (i32 i = 1; i <= n; ++i) {
    i32 a;
    scanf ("%" SCNi32, &a);
    add (bit, i, a);
  }
  for (i32 i = 1; i < n; ++i) {
    set = merge (set, new_node (i));
  }
  while (q--) {
    i32 t, x;
    scanf ("%" SCNi32 "%" SCNi32, &t, &x);
    if (t == 1) {
      node *z[4] = {NULL, NULL, NULL, NULL};
      split (set, x, z + 0, z + 1);
      split (z[0], x - 1, z + 2, z + 3);
      set = merge (z[2], z[1]);
      free_node (z[3]);
    } else if (t == 2) {
      node *z[4] = {NULL, NULL, NULL, NULL};
      split (set, x, z + 0, z + 1);
      split (z[0], x - 1, z + 2, z + 3);
      if (z[3] == NULL) z[2] = merge (z[2], new_node (x));
      set = merge (z[2], z[1]);
    } else if (t == 3) {
      add (bit, x, 1);
    } else {
      node *z[4] = {NULL, NULL, NULL, NULL};
      split (set, x - 1, z + 0, z + 1);
      i32 l = find_max (z[0]);
      i32 r = find_min (z[1]);
      i64 ans = get_sum (bit, MIN(r, n)) - get_sum (bit, MAX(l, 0));
      printf ("%" PRIi64 "\n", ans);
      set = merge (z[0], z[1]);
    }
  }
}

int main (void) {
  run();
  return 0;
}
0