Codeforces ECR #090 : G. Pawns

また妙な問題設定。
https://codeforces.com/contest/1373/problem/G

問題

N*Nのチェスの盤面がある。
ここに、ポーンを追加・削除するクエリが与えられる。
クエリ後の以下の値を求めよ。

各ポーンは、次の行の同一列または隣接列に移動できる。
ただし、1マスに2つ以上のポーンは配置できない。
全ポーンがK列目に並べられるよう移動することを考える。
この時、盤面を下方向に伸ばせるとする。
全ポーンをK列目に収めるために、最小何行分盤面を伸ばす必要があるか。

解法

ポーンを(r,c)列に増減すると、K列目ではr+|K-c|以降の行に配置できることになる。
SegTreeを使い、ある行の区間中に配置されるポーンを置き切ろうとすると、区間を何行延長しなければならないかを更新していこう。

int N,K,M;
set<pair<int,int>> S;
int num[404040];

int NV=1<<20;
int len[1<<21],ma[1<<21];

void update(int entry, int v) {
	entry += NV;
	len[entry]=v;
	ma[entry]=(entry-NV)+v-1;
	
	while(entry>1) {
		entry>>=1;
		if(len[entry*2]==0) {
			ma[entry]=ma[entry*2+1];
		}
		else if(len[entry*2+1]==0) {
			ma[entry]=ma[entry*2];
		}
		else {
			ma[entry]=max(ma[entry*2+1],ma[entry*2]+len[entry*2+1]);
		}
		len[entry]=len[entry*2]+len[entry*2+1];
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>M;
	while(M--) {
		cin>>x>>y;
		int t=y+abs(K-x);
		if(S.count({x,y})) {
			S.erase({x,y});
			num[t]--;
		}
		else {
			S.insert({x,y});
			num[t]++;
		}
		update(t,num[t]);
		
		if(len[1]==0) {
			cout<<0<<endl;
		}
		else {
			x=ma[1];
			cout<<max(0,x-N)<<endl;
		}
	}
}

まとめ

ECRのGにしては実装が軽め。