結果

問題 No.833 かっこいい電車
ユーザー akakimidori
提出日時 2019-05-24 22:35:01
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 4,285 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 34,164 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-07-02 03:44:11
合計ジャッジ時間 3,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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* new_node (const i32 val) {
  node *t = (node *) calloc (1, sizeof (node));
  *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);
  free (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;
}
void print_set (node *r) {
  if (r == NULL) return;
  print_set (r->left);
  printf ("%" PRIi32 " ", r->val);
  print_set (r->right);
}
#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);
  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);
  }
  node *set = NULL;
  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[3] = new_node (x);
      set = merge (merge (z[2], z[3]), 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0