Codeforces #569 Div1 C. Serge and Dining Room

ちょっと問題文が長い。
https://codeforces.com/contest/1179/problem/C

問題

N個の料理があり、それぞれの価格はA[i]である。各料理は1人分しかない。
ここにM人の生徒が順に並んでいる。各生徒はお金をB[i]だけ持っている。
生徒は、残された料理のうち、自身のお金で払える最高額の物を買う。

以下の各クエリに求めよ。

• 料理の価格または生徒の所持金を1つ指定に応じて変える。その場合、最後に残された料理の価格を答えよ。

解法

問題文では生徒の並び順が意味ありげに書かれているが、実際は並び順は関係ない。
とすると、ある金額Xについて、X以下の料理がX以下の学生よりも多いならばXの料理が最後に残る。
あとはこのXの最大値を求めよう。

区間加算ができるSegTreeを用意し、料理A[i]に対し[0,A[i]]に1加算、生徒B[i]に対し[0,B[i]]に1減算を行う。
そうすると値が1以上となるkeyの最大値を求められれば良いので、そのようなSegTreeを書こう。

int N,M,Q;
ll A[303030],B[303030];

template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int v,int l=0,int r=NV,int k=1) {
		if(v+ma[k]<=0) return -1;
		if(l+1==r) return l;
		
		if(v+val[k]+ma[2*k+1]>0) return getval(v+val[k],(l+r)/2,r,k*2+1);
		return getval(v+val[k],l,(l+r)/2,k*2);
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		st.update(0,A[i]+1,1);
	}
	FOR(i,M) {
		cin>>B[i];
		st.update(0,B[i]+1,-1);
	}
	cin>>Q;
	int cur=0;
	while(Q--) {
		cin>>i>>x>>y;
		x--;
		if(i==1) {
			st.update(0,A[x]+1,-1);
			A[x]=y;
			st.update(0,A[x]+1,1);
		}
		else {
			st.update(0,B[x]+1,1);
			B[x]=y;
			st.update(0,B[x]+1,-1);
		}
		
		int cur=st.getval(0);
		if(cur<=0) cur=-1;
		
		cout<<cur<<endl;
	}
	
	
	
}

まとめ

問題文は長いけど、問題自体は悪くないね。