ちょっと問題文が長い。
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; } }
まとめ
問題文は長いけど、問題自体は悪くないね。