AOJ0553 Dungeon
おなじみのダンジョン。
各階ごとに、死にそうだったらそこまでで一番多く回復できるところで回復したことにして続ける。
そこで、「ある場所以降すべてにある値を足す」「ある場所以降の最大値を求める」というクエリが処理できればいいことがわかって、これはstarry sky木でできる。
starry sky木を実装したのは初めてで、普通の遅延評価木と同じだと思ってたらflagの更新法を間違えてたのでだいぶ時間をとられてしまった。本番じゃなくてよかった...
segtreeもっと慣れないと死んでしまいます。
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #define SIZE 131072 using namespace std; typedef long long ll; typedef pair<ll,ll>pii; class segtree { public: ll seg[SIZE*2]; ll flag[SIZE*2]; ll update(int beg,int end,int node,int lb,int ub,ll num) { if(ub<beg||end<lb) { return seg[node]; } if(beg<=lb&&ub<=end) { flag[node]+=num; return seg[node]=seg[node]+num; } if(flag[node]) { flag[node*2]+=flag[node]; flag[node*2+1]+=flag[node]; seg[node*2]+=flag[node]; seg[node*2+1]+=flag[node]; flag[node]=0; } return seg[node]=max(update(beg,end,node*2,lb,(lb+ub)/2,num),update(beg,end,node*2+1,(lb+ub)/2+1,ub,num)); } ll query(int beg,int end,int node,int lb,int ub) { if(ub<beg||end<lb) { return -1000000000000000000LL; } if(beg<=lb&&ub<=end) { return seg[node]; } if(flag[node]) { flag[node*2]+=flag[node]; flag[node*2+1]+=flag[node]; seg[node*2]+=flag[node]; seg[node*2+1]+=flag[node]; flag[node]=0; } return max(query(beg,end,node*2,lb,(lb+ub)/2),query(beg,end,node*2+1,(lb+ub)/2+1,ub)); } }; segtree seg; int main() { ll num,gen; scanf("%lld%lld",&num,&gen); seg.update(0,SIZE-1,1,0,SIZE-1,gen); ll ret=0; priority_queue<pii>que; for(int i=0;i<num-1;i++) { ll za,zb; scanf("%lld%lld",&za,&zb); que.push(make_pair(zb,i)); for(;;) { if(que.empty()) { break; } if(seg.query(i+1,i+1,1,0,SIZE-1)-za>0) { break; } pii zan=que.top(); ll ka=(gen-seg.query(zan.second,i+1,1,0,SIZE-1))/zan.first,kb=(1-seg.query(i+1,i+1,1,0,SIZE-1)+za+zan.first-1)/zan.first; if(ka>=kb) { ret+=kb; seg.update(zan.second,SIZE-1,1,0,SIZE-1,kb*zan.first); } else { ret+=ka; que.pop(); que.push(make_pair((gen-seg.query(zan.second,i+1,1,0,SIZE-1))%zan.first,zan.second)); seg.update(zan.second,SIZE-1,1,0,SIZE-1,ka*zan.first); } } seg.update(i+1,SIZE-1,1,0,SIZE-1,-za); } printf("%lld\n",ret); }
この問題ad-hocって聞くし自分にとってはぜんぜんad-hocじゃなくて思いっきりデータ構造+シュミレーションだったんだけどほかの人たちどうしてるんだろう。