ACM-ICPC 2016 Asia Tsukuba Regional, G 解法

G: Placing Medals on a Binary Tree

問題

深さ10^9の完全二分木がある。根の深さは0、葉の深さは10^9。n個のメダルを順番に頂点に置いていく。このとき、部分木にメダルがある頂点には置くことができない。また頂点の深さはメダルに書かれている数と等しくなければならない。すでに置いてあるメダルを深さを変えずに他の頂点に移してもよい。
メダルを順番に置けるなら置いていく。それぞれ、置いたらYes。そうでないならNoを出力せよ。
n <= 5 * 10^5

解法

xと書かれたメダルが2枚あるとき、兄弟同士に置くことでx-1のメダルと同等になる。よって、同じ数のメダルは高々1つしか置いていない状況を管理する。
新しいメダルを置こうとしたときに、0のメダルができて他にもメダルがあるとそのメダルは置くことができない。また0のメダルがあるときはそれ以上メダルを置くことができない。
大きい数の書かれたメダルは0のメダルに成ることはないので、置いたかどうかだけ覚えておけばいい。具体的にはnより大きいと十分。
メダルを置くと0のメダルができるかどうかの判定はFenwick Treeで良さそう。

コード

#include<assert.h>
#include<set>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T>
struct Fenwick : vector<T> {
    typedef vector<T> S;
    int N;
    Fenwick(int N_=0): S(N_), N(N_) {}
    void add(int i, T x) {
	for (; i<N; i|=i+1) S::operator[](i) += x;
    }
    inline T sum(int r) {
	T s = 0;
	for (; r; r&=r-1) s += S::operator[](r-1);
	return s;
    }
    T sum(int l, int r) {
	return sum(r) - sum(l);
    }
};

int N;
int X[500111];
const int MAGIC = 1000000;
Fenwick<int> F(MAGIC);
int large;

int main() {

    scanf("%d", &N);
    REP (i, N) scanf("%d", X+i);

    REP (i, N) {
	bool yes;
	if (F.sum(0, 1) == 1) {
	    yes = false;
	} else if (MAGIC <= X[i]) {
	    yes = true;
	    large++;
	} else if (F.sum(0, X[i]+1) < X[i]) {
	    yes = true;
	    int k;
	    for (k=X[i]; F.sum(k, k+1); k--) F.add(k, -1);
	    F.add(k, 1);
	} else if (F.sum(0, X[i]+1) == X[i]) {
	    if (large || F.sum(X[i]+1, MAGIC)) yes = false;
	    else {
		yes = true;
		for (int k=1; k<=X[i]; k++) F.add(k, -1);
		F.add(0, 1);
	    }
	} else {
	    assert(false);
	}

	puts(yes? "Yes": "No");
    }

    return 0;
}