Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1956-d9c55bd6
この記事にトラックバックする(FC2ブログユーザー)

April 2011 Challenge 4問目 - Gravel (この記事を編集する[管理者用])

Source

codechef April 2011 Challenge 4問目
Problem Statement
April 2011 Challengeの参加記録

問題概要

n個 (10^6以下) の山にそれぞれ最初c個 (10^9以下) の石が積んである.
やるべき操作がm回 (250000以下) 与えられるので,それを行う問題.
 u番目~v番目の山にそれぞれk個の石を加える
 p番目の山の石の数を答える

解法

Fenwick tree.
増減の配列だけ用意しておいて,各山の石の個数は,ここから左の配列の和という形にする.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

typedef struct struct_intfenwick{
  int size, memory;
  ll *data;
}intFenwickTree;

intFenwickTree intFenwickTreeNew(int memory){
  intFenwickTree res;
  res.memory=memory; res.data=(ll*)malloc(memory*sizeof(ll));
  return res;
}

void intFenwickTreeDelete(intFenwickTree *t){free(t->data);}
void intFenwickTreeInit(intFenwickTree *t, int size){int i; t->size=size; rep(i,size) t->data[i]=0;}
void intFenwickTreeAdd(intFenwickTree *t,int k,ll add){while(k<t->size)t->data[k]+=add, k|=k+1;}
ll intFenwickTreeGet(intFenwickTree *t,int k){ll res=0; while(k>=0)res+=t->data[k],k=(k&(k+1))-1; return res;}

int main(){
  int i,j,k,l,m,n,c;
  intFenwickTree t = intFenwickTreeNew(1111111);
  ll res;
  char mode[100];

  scanf("%d%d%d",&n,&m,&c);
  intFenwickTreeInit(&t,n+4);
  intFenwickTreeAdd(&t,0,c);

  while(m--){
    scanf("%s",mode);
    if(mode[0]=='Q'){
      scanf("%d",&k); k--;
      res = intFenwickTreeGet(&t,k);
      printf("%lld\n",res);
    } else {
      scanf("%d%d%d",&i,&j,&k); i--; j--;
      intFenwickTreeAdd(&t,i,k);
      intFenwickTreeAdd(&t,j+1,-k);
    }
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1956-d9c55bd6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。