高さが無限大,幅が $W$ の2次元のグリッドがある.
AさんとBさんが順番に以下の行動を行う.
今,$N$ 番目の手順まで,$i$ 番目の手順では,$A_i \times B_i$ のブロック塊を $X_i$ 列から $X_i+A_i-1$ 列に重なるように置いたという情報が与えられる.
$N$ 番目の手順が終わった時点で,全ての列には $H$ 個以上の $1 \times 1$ ブロックが置かれていることが保証されている.
どちらが勝ったか求める問題.
セグメントツリーを使いながら愚直にシミュレーションする.
具体的には長さ $W$ の配列を扱えるセグメントツリーを用意し,ブロックを置いたときは,$X_i$ から $X_i+A_i-1$ 番目の要素に $B_i$ を足す.
そして,要素の最大値を調べて $H$ 以上であれば,今のターンの人に $1$ 点を与えて,その要素にマイナス無限大を加えてやれば良い(これは最大値が $H$ 未満になるまで繰り返す).
時間計算量は $O((N+W) \log W)$ 程度.
C++に変換後のコードはこちら
int A[100000], B[100000], X[100000];
{
int i, k;
ll N, W, H;
segtree<ll> t;
pair<ll,int> mn;
ll res[2] = {0LL, 0LL};
rd(N,W,H,(A,B,X)(N));
X[0..N-1]--;
t.malloc(W, 1);
rep(i,N){
t.add(X[i], X[i]+A[i], -B[i]);
for(;;){
mn = t.getMin(X[i], X[i]+A[i]);
if(mn.first > -H) break;
k = mn.second;
res[i%2]++;
t.add(k,k+1,1d18);
}
}
if(res[0] > res[1]) wt("A");
if(res[0] < res[1]) wt("B");
if(res[0]==res[1]) wt("DRAW");
}
Current time: 2024年04月26日06時42分13秒
Last modified: 2017年04月30日01時17分55秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)