TopCoder SRM 834 : Div1 Medium ItsWhomYouKnow

何がしたい問題なんだろう。
https://community.topcoder.com/stat?c=problem_statement&pm=17757

問題

病院の待合室には、すでに何人かの人がいる。
また、1人診察している間に2人新規の病人が待合室に来る。

各病人は、所属グループと強さの2パラメータを持つ。
次に診察する人は、以下のように決まる。

• 待合室1人以上いるグループのうち、過去診察室に入った人のうち最大の強さを持つグループを選び、その中で一番長い間待っている人を選ぶ。

N人診察する場合、それぞれどの人が診察されるか答えよ。
なお、この問題はオンラインクエリとなっており、診察する人を答えないと、次に来る2名の病人のパラメータが確定しない。

解法

考え方自体は単純で、以下3つをクエリ毎に処理すればよい。

• 各グループにおける、待合室にいる人の一覧をキューで持つ
• 各グループにおける、過去待合室に入った人の強さの最大値
• 待合室に1人以上人がいるグループについて、強さの最大値をとるsetやpriority_queue

愚直に行うと1つ問題がある。
この問題はグループ数が最大10^6あるが、C++のSTL queueを10^6個作るとMLEしてしまう。
考えられる解法は以下の2つ。以下のコードは後者である。

• 診察室に来る人は2N人強なので、必要な分だけキューを作る
• STLのqueueを使わず、linked-list的な構造を自製する

ll C[303030];
ll P[303030];
int nex[303030];
int L[1303030],R[1303030];

ll powers[1303030];
set<pair<int,int>> cand;
ll state;

class ItsWhomYouKnow {
	public:
	
	void add(int x) {
		int c=C[x];
		cand.erase({-powers[c],c});
		if(L[c]==-1) {
			L[c]=R[c]=x;
			nex[x]=-1;
		}
		else {
			nex[R[c]]=x;
			nex[x]=-1;
			R[c]=x;
		}
		powers[c]=max(powers[c],P[x]);
		cand.insert({-powers[c],c});
	}
	void del(int c) {
		L[c]=nex[L[c]];
		if(L[c]==-1) cand.erase({-powers[c],c});
	}
	long long simulate(int N, int C_, int P_, vector <int> initialClans, vector <int> initialPowers, int seed) {
		int i;
		cand.clear();
		FOR(i,C_) {
			L[i]=R[i]=powers[i]=-1;
		}
		FOR(i,initialClans.size()) {
			C[i]=initialClans[i];
			P[i]=initialPowers[i];
			add(i);
		}
		int nex=initialClans.size();
		state=seed;
		ll ret=0;
		int j;
		FOR(i,N) {
			FOR(j,2) {
				state = (state * 1103515245 + 12345)%(1LL<<31);
				C[nex]=state/10%C_;
				state = (state * 1103515245 + 12345)%(1LL<<31);
				P[nex]=state%P_;
				add(nex);
				nex++;
			}
			int c=cand.begin()->second;
			ret+=1LL*(i+1)*L[c];
			state=(state+L[c])%(1LL<<31);
			del(c);
		}
		return ret;
		
		
	}
}

まとめ

本番これ出てたらqueueを10^6個作ってMLEしてたな…。