結果

問題 No.789 範囲の合計
コンテスト
ユーザー akakimidori
提出日時 2019-05-25 04:47:30
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 141 ms / 1,000 ms
コード長 1,253 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 29,952 KB
実行使用メモリ 33,280 KB
最終ジャッジ日時 2024-09-17 15:01:46
合計ジャッジ時間 3,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef int32_t i32;
typedef int64_t i64;

typedef struct segment_node {
  struct segment_node *left;
  struct segment_node *right;
  i32 sum;
} node;

node* add (node *t, i32 l, i32 r, i32 x, i32 y) {
  if (t == NULL) {
    t = (node *) calloc (1, sizeof (node));
    *t = (node) {NULL, NULL, 0};
  }
  t->sum += y;
  if (l + 1 == r) {
    return t;
  }
  i32 m = (l + r) / 2;
  if (x < m) {
    t->left = add (t->left, l, m, x, y);
  } else {
    t->right = add (t->right, m, r, x, y);
  }
  return t;
}

i32 query (node *t, i32 l, i32 r, i32 x, i32 y) {
  if (t == NULL || y <= l || r <= x) {
    return 0;
  }
  if (x <= l && r <= y) {
    return t->sum;
  }
  i32 m = (l + r) / 2;
  return query (t->left, l, m, x, y) + query (t->right, m, r, x, y);
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  const i32 l = 0;
  const i32 r = 1000000000 + 1;
  node *s = NULL;
  i64 ans = 0;
  while (n--) {
    i32 t, x, y;
    scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &t, &x, &y);
    if (t == 0) {
      s = add (s, l, r, x, y);
    } else {
      ans += query (s, l, r, x, y + 1);
    }
  }
  printf ("%" PRIi64 "\n", ans);
}

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