結果
問題 | No.789 範囲の合計 |
ユーザー |
![]() |
提出日時 | 2019-02-08 21:44:21 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 122 ms / 1,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 127 ms |
コンパイル使用メモリ | 29,952 KB |
実行使用メモリ | 33,280 KB |
最終ジャッジ日時 | 2024-06-28 18:40:58 |
合計ジャッジ時間 | 2,013 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include<stdio.h>#include<stdlib.h>typedef long long int int64;typedef struct node{int sum;struct node *l,*r;} node;node* newNode(void){node *t=(node *)calloc(1,sizeof(node));t->sum=0;t->l=t->r=NULL;return t;}node* add(node *t,int l,int r,int index,int v){if(index<l || r<=index) return t;if(t==NULL) t=newNode();t->sum+=v;if(l+1==r) return t;int m=(l+r)/2;if(index<m){t->l=add(t->l,l,m,index,v);} else {t->r=add(t->r,m,r,index,v);}return t;}int sum(node *t,int l,int r,int x,int y){if(t==NULL) return 0;if(y<=l || r<=x) return 0;if(x<=l && r<=y) return t->sum;int m=(l+r)/2;return sum(t->l,l,m,x,y)+sum(t->r,m,r,x,y);}void run(void){int n;scanf("%d",&n);node *t=NULL;int l=0;int r=1000000001;int64 ans=0;while(n--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0){t=add(t,l,r,x,y);} else {ans+=sum(t,l,r,x,y+1);}}printf("%lld\n",ans);}int main(void){run();return 0;}