Codeforces 420 Coder-Strike 2014 - Finals (online edition, Div. 1) D. Cup Trick

問題

n個のコップがあり、それぞれ1〜nの番号がついている。
最初順番がバラバラになって一列に並んでいる。

これに対してm回操作をした記録が与えられる。i番目の操作はx[i], y[i]により表され、
左からx[i]番目のコップにはy[i]の番号がかかれていて、
それを列から取り除いて列の左端に加えたことを意味する。

この記録が正しいような初期状態における番号の並びをどれか一通り求めよ。
存在しない場合はそれを出力せよ。

制約条件

n, m≦10^5

方針

途中の要素の削除、末尾に要素の追加が短い時間でできるデータ構造を使って、
コップの動きをシミュレートすればよい。
一般的にはsplit-mergeの平衡二分木とかを使えばよい。

途中に要素の挿入がないので、単にvectorでデータを持って、
要素が存在する場所をbinary indexed treeを管理し、
フラグのたってない場所は無視するようにすればいい。
i番目のフラグの立っている場所を見つけるにはbinary indexed treeを二分探索すればよくて、
これはO(log n)で出来る。

ソースコード

const int MX = 1 << 21;
int bit[MX];
inline int sum(int i){
	int res = 0;
	for(i++; i; i -= i & -i) res += bit[i];
	return res;
}
inline void add(int i, int x){
	for(i++; i < MX; i += i & -i) bit[i] += x;
}
inline int find(int k){
	int lo = 0, hi = MX, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(bit[mid] >= k) hi = mid;
		else lo = mid, k -= bit[mid];
	}
	return hi - 1;
}

int n, m;
int ans[MX];
vector<pi> v;

int main(){
	bool ok = 1;
	
	scanf("%d%d", &n, &m);
	v.resize(n);
	rep(i, n){
		v[i] = mp(n - i - 1, -1);
		add(i, 1);
	}
	
	rep(i, m){
		int x, y;
		scanf("%d%d", &x, &y);
		y--;
		
		int pos = find(n - y);
		if(v[pos].second >= 0 && v[pos].second != x) ok = 0;
		v[pos].second = x;
		
		v.pb(v[pos]);
		v[pos] = mp(-1, -1);
		add(pos, -1);
		add(n + i, 1);
	}
	
	memset(ans, -1, sizeof(ans));
	set<int> unused;
	
	rep(i, n) unused.insert(i + 1);
	rep(i, n){
		int pos = find(n - i); 
		
		//dbg(pos);
		//cerr<<v[pos].first<<" "<<v[pos].second<<endl;
		
		if(v[pos].second < 0) continue;
		if(ans[v[pos].first] >= 0 || !unused.count(v[pos].second)) ok = 0;
		
		ans[v[pos].first] = v[pos].second;
		unused.erase(v[pos].second);
	}
	
	if(!ok){
		puts("-1");
		return 0;
	}
	
	rep(i, n){
		if(ans[i] < 0){
			ans[i] = *unused.begin();
			unused.erase(unused.begin());
		}
		printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
	}
	
	
	return 0;
}