[ABC245] E - Wrapping Chocolate

[Q] https://atcoder.jp/contests/abc245/tasks/abc245_e

setだとWA。multisetだよ。

1. チョコは{A, B}でsort
2. 箱は{C, D}でsort
3. Aの大きいチョコから処理する。
4. A以上の箱Cについて、Cの相方のDをすべてmultisetに収める。
5. 候補のmultisetの中で、Bを満たす最小のDを使えば、最も効率よく箱を選べる。

choco=2 box=3
A: 2 4
B: 3 2
C: 8 1 5
D: 2 10 5

1. チョコはAでsort、箱はCでsortする。
choc[] = {{2,3}, {4,2}} // A,B
box[] = {{1,10}, {5,5}, {8,2}} // C,D

2. Aが大きいチョコから処理する。
・choc[1]: {4,2}
C>=4を満たす箱について、Dの値をおさめていく。

box[2]: {8,2} は 4<=8 で採用
multiset = {2}
box[1]: {5,5} は 4<=5 で採用
multiset = {2, 5}
box[0]: {1,10} は 4>1 で不採用

multiset: {2, 5}の中で、B=2以上を探索する。
D=2が条件を満たす最小値なので、採用。

2を使うので
multiset: {5} 

・choc[0]: {2,3}
box[0]: {1,10} は 2>1 で不採用
multiset: {5}の中で、B=3以上を探索する。
D=5が条件を満たす最小値なので、採用。

multiset: {}

すべてのチョコレートが包装できたので Yes

実装

int main(){
 cincout();
 
 ll N, M;
 cin >> N >> M;
 // Aの大きい値から処理
 // A以上のCをいったん全部いれる。
 // もっとも小さいDを削除。
 vector<pll> choc(N);
 vector<pll> box(M);
 rep(i, N){ cin >> choc[i].first; }
 rep(i, N){ cin >> choc[i].second; }
 rep(i, M){ cin >> box[i].first; }
 rep(i, M){ cin >> box[i].second; }
 sort(all(choc));
 sort(all(box));
 
 ll j = M-1;
 multiset<ll> S; // d
 for(ll i=N-1; i>=0; --i){
   auto [a, b] = choc[i]; // 上から
   while (j>=0 && box[j].first >= a){
     S.insert(box[j].second); 
     --j;
   }
   auto it = S.lower_bound(b);
   if (it == S.end()){
     cout << "No" << endl;
     return 0;
   }
   S.erase(it);
 }
 cout << "Yes" << endl;
}

https://atcoder.jp/contests/abc245/submissions/30514653