yukicoder : No.59 鉄道の旅

☆３つだけどだいぶ簡単。
http://yukicoder.me/problems/98

問題

電車がN個の駅を順に通る。
各駅では、重さW[i]の荷物を積むか、W[i]の荷物を降ろす指示が与えられる。

ただし荷物を積む場合、既にW[i]以上の重さの荷物がK個以上あったらその荷物は積むことができない。
最終的に電車には何個の荷物が積まれるか。

解法

BITで重さW[i]以上の荷物の数を数えればよい。
また、その際重さがちょうどW[i]の荷物の数もカウントしておくと、荷物を降ろす際に「W[i]ちょうどの荷物があるか」の判定が容易になる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> bt;

int N,K;
int W[1000001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		if(x>0) {
			if(bt.total(1<<20)-bt.total(x-1)<K) bt.update(x,1),W[x]++;
		}
		else {
			if(W[-x]) W[-x]--, bt.update(-x,-1);
		}
	}
	cout << bt.total(1<<20) << endl;
	
}

まとめ

BITを知らないと難しいけど、ライブラリ化されていると☆２個相当。