Submission

Score: 100

User: qweqwe

Problemset: ถังดักนิวทริโน

Language: cpp

Time: 0.004 second

Submitted On: 2026-02-25 21:28:58

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

vector<ll> parents;
vector<vector<ll>> allParents;

void findLastParent(int n,int i){
	allParents[i].push_back(parents[n]);
	if (parents[n]==0) return;
	if (n==parents[n]) return;
	findLastParent(parents[n],i);
}

int main(){
	fastio;
	int n,m;
	cin >> n >> m;
	
	parents.resize(n+1);
	allParents.resize(n+1);
	vector<vector<ll>> buckets(n+1);
	
	vector<ll> intervals(100001,0);
	for (int i=1;i<=n;i++){
		ll st,en;
		cin >> st >> en;
		
		parents[i] = intervals[st];
		for (int j=st;j<=en;j++){
			intervals[j] = i;
		}
		findLastParent(parents[i],i);
		vector<ll> grandParents = allParents[i];
		
		buckets[parents[i]].push_back(i);
		/*
		for (ll j:parents){
			cout << j << " ";
		}cout << "\n";
		*/
		for (ll grandParent:grandParents){
			//cout << grandParent << " ";
			if (grandParent != parents[i])buckets[grandParent].push_back(i);
		}//cout << "\n";
		buckets[i].push_back(i);
	}
	
	unordered_set<ll> req;
	for (int i=0;i<m;i++){
		int q;
		cin >> q;
		req.insert(q);
	}
	
	vector<ll> pickedBuckets;
	
	while (!req.empty()){
		ll minAllBucket = 0, maxReqBucket = 0, index = -1;
		
		for (int i=1;i<=n;i++){
			ll tempBucket = 0;
			for (int j:buckets[i]){
				if (req.count(j)){
					tempBucket++;
				}
			}
			
			ll curBucket = (ll)buckets[i].size();
			
			if (tempBucket >= maxReqBucket){
				if (tempBucket == maxReqBucket){
					if (minAllBucket > curBucket){
						minAllBucket = curBucket;
						index = i;
					}
				}else{
					minAllBucket = (ll)buckets[i].size();
					maxReqBucket = tempBucket;
					index = i;
				}
			}
			//cout << i << " " << minAllBucket << " " << maxReqBucket << " " << index << "\n";
		}
		for (int j:buckets[index]){
			if (req.count(j)){
				req.erase(j);
			}
		}
		pickedBuckets.push_back(index);
	}
	sort(pickedBuckets.begin(),pickedBuckets.end());
	cout << pickedBuckets.size() << "\n";
	for (ll i:pickedBuckets){
		cout << i << " ";
	}
	
	return 0;
}