T4

50pts，数组模拟时间区间的变化

#include <bits/stdc++.h>  
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  

/*
优先安排 病情严重度最小的人 的治疗时间

安排开始时间时，应该让他最快得到治疗

维护一个数据结构，记录所有空闲的时间段
t[i]  记录时刻i是否有时间
按照病情严重度从小到大 安排所有病人的时间段

在所有空闲的时间段中，找到最快能够治疗这个病人的时间段
*/

const int N = 1e5+5;  

struct P {
	int p, t, a, b;
	
	// 重载运算符
	bool operator < (const P & other) const {
		return p < other.p;
	}
};

struct T {
	int l, r;  // 记录区间 [l, r] 的时间段
};

int n, k;
P a[N];
vector<T> mp;
// t到的时间  a钱  b治疗需要的时间

int findidx(P x) {
	// 查找病人x能安排的时间段，返回这个时间段的下标
	for (int i=0; i<mp.size(); i++) {
		// t1 开始治疗的时间  max(t,mp[i].l)  t2 结束治疗的时间
		int t1 = max(x.t, mp[i].l), t2 = t1+x.b-1;
		if (t2 <= mp[i].r) return i;
	}
	return -1;
}

signed main() {  
//	freopen("op.in", "r", stdin);
//	freopen("op.out", "w", stdout);
	qwq;  
	
	cin >> n >> k;
	for (int i=1; i<=n; i++) cin >> a[i].p;
	for (int i=1; i<=n; i++) cin >> a[i].t;
	for (int i=1; i<=n; i++) cin >> a[i].a;
	for (int i=1; i<=n; i++) cin >> a[i].b;
	
	sort(a+1, a+1+n);
	
	int res = 0;
	
	mp.push_back({1, k});  // 初始时间段
	
	for (int i=1; i<=n and mp.size(); i++) {  // 安排第i名病人的时间段
		// 找是否有时间段可以安排这个病人
		int idx = findidx(a[i]);
		if (idx == -1) {  // 没救了
			// a[i].t 往后的所有时间段，都被删除
			while (mp.size() and mp.back().l >= a[i].t) mp.pop_back();
			// 处理交叉的情况
			if (mp.size() and mp.back().r >= a[i].t) mp.back().r = a[i].t-1;
			continue;
		}
		// 有救的情况
		res += a[i].a;  // 钱拿走
		
		int t1 = max(a[i].t, mp[idx].l), t2 = t1+a[i].b-1;   // t1开始救的时间 t2 结束的时间
		// 下标是idx的区间删掉  [mp[idx].l, t1-1] [t2, mp[idx].r]
		vector<T> temp;  // 临时用于辅助删除的数组
		
		for (int j=0; j<mp.size(); j++) {
			if (mp[j].r < a[i].t or mp[j].l > t2) temp.push_back(mp[j]);
			else {
				if (mp[j].l < a[i].t) temp.push_back({mp[j].l, a[i].t-1});
				if (mp[j].r > t2) temp.push_back({t2+1, mp[j].r});
			}
		}
		
		mp = temp;
	}
	
	cout << res;
	return 0;  
}

100pts

#include <bits/stdc++.h>  
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
using namespace std;  

/*
4 4
1 2 3 4
3 1 1 2
1 2 3 4
2 1 1 2
无论如何，严重度越高，一定先要治疗，否则会医闹
也就是说，应该按照严重程度排序，然后根据他们到达
的时间安排治疗的顺序，当前病人应该最快时间得到治疗。

最开始手术时间 [1, k]
[a1, b1]

[1, a1-1]  [b1+1, k]

[a2, b2]

需要维护所有可以动手术的区间时间
并且可以快速查找到当前病人第一个可以动手术的区间的位置
并且可以快速更新当前病人动手术后的区间情况

50pts，n^2即可，直接数组模拟

如何满分？

set可以实现logn查找和logn删除
*/

const int N = 1e5+5;  

struct P {
	int p, t, a, b;
	
	bool operator < (const P &b1) const {
		return p < b1.p;
	}
};

struct T {
	int l, r, t;  // t用来表示是正常元素比较还是二分比较
	bool operator < (const T & b1) const {
		if (b1.t == 0) return l < b1.l;  // 正常比较
		else return max(l, b1.l) + b1.r - 1 > r;  // 用于二分的比较
	}
};

int n, k, sum;
P a[N];
set<T> tq;

void show() {
	for (auto x : tq) cout << "{" << x.l << " " << x.r << "} ";
	cout << '\n';
}

signed main() {  
//	freopen("op.in", "r", stdin);
//	freopen("op.out", "w", stdout);
	qwq;  
	
	cin >> n >> k;
	for (int i=1; i<=n; i++) cin >> a[i].p;
	for (int i=1; i<=n; i++) cin >> a[i].t;
	for (int i=1; i<=n; i++) cin >> a[i].a;
	for (int i=1; i<=n; i++) cin >> a[i].b;
	
	sort(a+1, a+1+n);  // 按严重程度排序
	
	tq.insert({1, k, 0});
	
	for (int i=1; i<=n and tq.size(); i++) {
//		show();
		auto idx = tq.lower_bound( T{a[i].t, a[i].b, 1} );  // 找到第一个可以开始时间大于等于 a[i].t 的
		auto idx2 = tq.lower_bound( T{a[i].t, a[i].b, 0} );  // 找到所有在 a[i].t 之后的区间，这些都删掉
		
		if (idx == tq.end()) {  // 找不到，说明当前病人无法得到治疗，所有时间在 t 之后的都不行
			// 对idx2进行处理
			vector<T> tmp;  // 要删除的区间序列
			T zz = {-1, -1, -1};
			if (idx2 != tq.begin()) {
				idx2--;  // 最后一个时间小于t的区间，要处理交叉的情况
				if (idx2->r >= a[i].t) {  // 有交叉的情况
					int l = idx2->l, r = idx2-> r;
					zz = {l, a[i].t-1, 0};
				}
			}
			while (idx2 != tq.end()) {
				tmp.push_back(*idx2);
				idx2++;
			}
			for (auto x : tmp) tq.erase(x);  // 删除所有无效时间
			if (zz.l != -1) tq.insert(zz);
		}
		else {  // 可以治疗，区间如何变化？
			sum += a[i].a;
			int l = idx->l, r = idx->r, t2 = max(l, a[i].t)+a[i].b-1;
			tq.erase(idx);  // 删除当前区间 logn，区间势必是包含关系
			if (l < a[i].t) tq.insert({l, a[i].t-1, 0});
			if (r > t2) tq.insert({t2+1, r, 0}); 
		}
	}
	
	cout << sum;
	return 0;  
}