$300$ $pits$

T4 手术

错误原因 ： 没有认真打草稿，思路不清楚

solution

算法 ：贪心 $+$ 模拟

用一个 $set$ 来维护 $[1 , k]$ 的区间

1. 先根据病情的严重程度来 $sort$

2. 先在 $set$ 中插入一个 $[1 , k]$ 的区间，表示总共能进行手术的时间

3. 对于每一个病人来说

   $(1)$ 用二分 $(lower$_$bound)$ 找到 $set$ 中 $<=$ 病人来到时间的第一个区间，再更新病人做手术的时间

   $(2)$ 如果病人做手术的时间不超过区间结尾，且若时间在区间内，那么将区间分为两段，为 $(l$ , $pre[i].t - 1)$ 和 $(pre[i].t$ , $r)$ $pre[i].t$ w为病人手术开始时间，继续用二分 $(lower$_$bound)$ 找到 $set$ 中 $<=$ 病人手术时间的第一个区间

   $(3)$ 遍历整个 $set$ , 寻找那些可以做手术的区间，具体的 $r - l + 1 >= pre[i].b$
   $pre[i].b$ 为手术持续时间

   $(4)$ 可以：则删除手术持续时间，统计答案，添加剩余时间

   $(5)$ 不可以：删除当前区间，继续找

code

#include<bits/stdc++.h>
#define int long long
#define ft first 
#define sd second 
using namespace std;

const int N = 1e5 + 5;

struct node{
	int p , t , a , b;
}pre[N];

int n , k;
set<pair<int , int> > s;

bool cmp(const node &lhs , const node &rhs){
	return lhs.p < rhs.p;
}

signed main(){
	freopen("op.in" , "r" , stdin);
	freopen("op.out" , "w" , stdout);
	
	cin >> n >> k;
	
	for(int i = 1 ; i <= n ; i ++) cin >> pre[i].p;
	for(int i = 1 ; i <= n ; i ++) cin >> pre[i].t;
	for(int i = 1 ; i <= n ; i ++) cin >> pre[i].a;
	for(int i = 1 ; i <= n ; i ++) cin >> pre[i].b;
	
	sort(pre + 1 , pre + n + 1 , cmp);
	s.insert({1 , k});
	
	int ans = 0;
	
	for(int i = 1 ; i <= n ; i ++){
		if(s.empty()) break;
		
		auto it = s.lower_bound({pre[i].t , 0});
		auto it2 = it;
		
		if(it2 != s.begin()) it2 --;
		if(pre[i].t >= it2 -> ft && pre[i].t <= it2 -> sd) it = it2;
		if(it != s.end()){
			pre[i].t = max(pre[i].t , it -> ft);
			
			if(pre[i].t <= it -> sd){
				
				if(it -> ft < pre[i].t){
					int l = it -> ft;
					int r = it -> sd;
					s.erase({l , r});
					s.insert({l , pre[i].t - 1});
					s.insert({pre[i].t , r});
					it = s.lower_bound({pre[i].t , 0});
				}
				vector<pair<int , int> > v;
				while(it != s.end()){
					int l = it -> ft;
					int r = it -> sd;
					
					if(r - l + 1 >= pre[i].b){
						ans += pre[i].a;
						s.erase(it);
						if(r - l + 1 > pre[i].b) s.insert({l + pre[i].b , r});
						break;
					}else{
						v.push_back({l , r});
						it ++;
					}
				}
				for(auto p : v) s.erase(p);
			}
		}
	}
	cout << ans << endl;
	return 0;
}